Find the Repeated Number in an Array
Solve this Problemnums of n + 1 integers, where every value lies between 1 and n. Exactly one value repeats — it might show up more than twice — while every other value appears exactly once. Find and return the repeated value.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ n ≤ 10⁵, where n + 1 = nums.length - ◆
1 ≤ nums[i] ≤ n - ◆
Exactly one value in nums repeats — it may appear more than twice — and every other value appears exactly once
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public int findDuplicateNumber(int[] nums) { |
| 3 | int slow = nums[0]; |
| 4 | int fast = nums[0]; |
| 5 | do { |
| 6 | slow = nums[slow]; |
| 7 | fast = nums[nums[fast]]; |
| 8 | } while (slow != fast); |
| 9 | |
| 10 | slow = nums[0]; |
| 11 | while (slow != fast) { |
| 12 | slow = nums[slow]; |
| 13 | fast = nums[fast]; |
| 14 | } |
| 15 | return slow; |
| 16 | } |
| 17 | } |
| 18 |
11Both slow and fast start at nums[0] = 1. slow will move one step at a time; fast will move two.
Approach & Solutions
Brute Force — Compare Every Pair
BruteCheck every pair of positions in the array. If two different positions hold the same value, that value is the repeat. Simple, but the nested loop does far more comparisons than necessary.
O(n²)O(1)1class Solution {
2 public int findDuplicateNumber(int[] nums) {
3 for (int i = 0; i < nums.length; i++) {
4 for (int j = i + 1; j < nums.length; j++) {
5 if (nums[i] == nums[j]) {
6 return nums[i];
7 }
8 }
9 }
10 return -1;
11 }
12}Better — Sort and Scan
BetterSort a copy of the array. Once sorted, any repeated value ends up sitting right next to its duplicate, so a single scan comparing each element to its predecessor finds it immediately. Faster to reason about than the pairwise brute-force check, and needs no extra hash structure — just the space the sort itself uses.
O(n log n)O(n)1class Solution {
2 public int findDuplicateNumber(int[] nums) {
3 int[] sorted = nums.clone();
4 Arrays.sort(sorted);
5 for (int i = 1; i < sorted.length; i++) {
6 if (sorted[i] == sorted[i - 1]) {
7 return sorted[i];
8 }
9 }
10 return -1;
11 }
12}Good — Hash Set
GoodWalk the array once, remembering every value seen so far in a set. The first value that's already in the set when you reach it again is the repeated one — return it immediately, no second pass needed.
O(n)O(n)1class Solution {
2 public int findDuplicateNumber(int[] nums) {
3 Set<Integer> seen = new HashSet<>();
4 for (int num : nums) {
5 if (!seen.add(num)) {
6 return num;
7 }
8 }
9 return -1;
10 }
11}Optimal — Floyd's Cycle Detection (Tortoise and Hare)
OptimalTreat each value as a pointer: index i points to index nums[i]. Since every value is between 1 and n and exactly one value repeats, following these pointers from index 0 is guaranteed to loop back on itself — a cycle — and the value where the cycle is entered is exactly the duplicate. Phase 1 (tortoise and hare): move slow one step and fast two steps until they meet somewhere inside the cycle — a meeting is guaranteed since fast gains on slow by one step every round. Phase 2: reset slow back to the start while leaving fast at the meeting point, then move both one step at a time; the spot where they meet again is exactly the entrance to the cycle — the duplicate. This uses no extra memory at all — the array itself is treated as a linked list.
O(n)O(1)1class Solution {
2 public int findDuplicateNumber(int[] nums) {
3 int slow = nums[0];
4 int fast = nums[0];
5 do {
6 slow = nums[slow];
7 fast = nums[nums[fast]];
8 } while (slow != fast);
9
10 slow = nums[0];
11 while (slow != fast) {
12 slow = nums[slow];
13 fast = nums[fast];
14 }
15 return slow;
16 }
17}