287. Find The Duplicate Number - Explanation

Description

You are given an array of integers nums containing n + 1 integers. Each integer in nums is in the range [1, n] inclusive.

There is exactly one repeated integer in nums, and every other integer appears at most once.

Return the repeated integer.

Example 1:

Input: nums = [1,2,3,2,2]

Output: 2

Example 2:

Input: nums = [1,2,3,4,4]

Output: 4

Follow-up: Can you solve the problem without modifying the array nums and using $O(1)$ extra space?

Constraints:

1 <= n <= 10,000
nums.length == n + 1
1 <= nums[i] <= n

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space without modifying the input array, where n is the size of the input array.

Hint 1

A naive approach would be to use a hash set, which provides O(1) average-time lookups but requires O(n) extra space. To avoid extra space, consider treating the array like a linked list: from an index i, the next index is nums[i]. Every value is in the range 1 to len(nums) - 1, so every value is also a valid index.

Hint 2

Since one value is repeated, multiple indices point to the same next index. Following the indices starting from index 0 must therefore lead to a cycle, whose entry corresponds to the duplicate value. Which algorithm can detect a cycle using constant extra space without modifying the array?

Hint 3

Use Floyd's cycle detection algorithm. Initialize a slow and a fast pointer at index 0. Repeatedly move the slow pointer one step with slow = nums[slow] and the fast pointer two steps with fast = nums[nums[fast]] until they meet. Is this first meeting point necessarily the duplicate?

Hint 4

The first meeting point may be anywhere inside the cycle. After the pointers meet, initialize a second slow pointer at index 0. Move both slow pointers one step at a time using the values in nums. The index where they meet is the cycle entry, which is the duplicate number.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Array Manipulation - Working with array indices and understanding value-to-index mappings
Hash Sets - Using sets for O(1) lookup to detect duplicates
Floyd's Cycle Detection - The fast and slow pointer technique for detecting cycles in linked list-like structures
Binary Search on Value Range - Applying binary search to count-based problems rather than sorted arrays

1. Sorting

Intuition

If we sort the array, any duplicate numbers will appear next to each other.
So after sorting, we just scan once and check if any two consecutive elements are equal.
The first equal pair we find is the duplicate.

Algorithm

Sort the array.
Loop through the array from index 0 to n - 2.
For each index i, check if nums[i] == nums[i + 1].
- If yes, return that value (this is the duplicate).
If no duplicate is found (theoretically impossible for this problem), return -1.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                return nums[i]
        return -1

public class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return nums[i];
            }
        }
        return -1;
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    findDuplicate(nums) {
        nums.sort((a, b) => a - b);
        for (let i = 0; i < nums.length - 1; i++) {
            if (nums[i] === nums[i + 1]) {
                return nums[i];
            }
        }
        return -1;
    }
}

public class Solution {
    public int FindDuplicate(int[] nums) {
        Array.Sort(nums);
        for (int i = 0; i < nums.Length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return nums[i];
            }
        }
        return -1;
    }
}

class Solution {
    fun findDuplicate(nums: IntArray): Int {
        nums.sort()
        for (i in 0 until nums.size - 1) {
            if (nums[i] == nums[i + 1]) {
                return nums[i]
            }
        }
        return -1
    }
}

class Solution {
    func findDuplicate(_ nums: [Int]) -> Int {
        var nums = nums.sorted()
        for i in 0..<nums.count - 1 {
            if nums[i] == nums[i + 1] {
                return nums[i]
            }
        }
        return -1
    }
}

impl Solution {
    pub fn find_duplicate(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        for i in 0..nums.len() - 1 {
            if nums[i] == nums[i + 1] {
                return nums[i];
            }
        }
        -1
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

2. Hash Set

Intuition

We can detect duplicates by remembering which numbers we have already seen.
As we scan the array, each new number is checked:

If it's not in the set, we add it.
If it is already in the set, that number must be the duplicate.

A set gives constant-time lookup, so this approach is simple and efficient.

Algorithm

Create an empty hash set seen.
Loop through each number in the array:
- If the number is already in seen, return it (this is the duplicate).
- Otherwise, insert the number into seen.
If no duplicate is found (should not happen in this problem), return -1.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                return num
            seen.add(num)
        return -1

public class Solution {
    public int findDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return num;
            }
            seen.add(num);
        }
        return -1;
    }
}

class Solution {
public:
    int findDuplicate(std::vector<int>& nums) {
        unordered_set<int> seen;
        for (int num : nums) {
            if (seen.find(num) != seen.end()) {
                return num;
            }
            seen.insert(num);
        }
        return -1;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    findDuplicate(nums) {
        let seen = new Set();
        for (let num of nums) {
            if (seen.has(num)) {
                return num;
            }
            seen.add(num);
        }
        return -1;
    }
}

public class Solution {
    public int FindDuplicate(int[] nums) {
        HashSet<int> seen = new HashSet<int>();
        foreach (int num in nums) {
            if (seen.Contains(num)) {
                return num;
            }
            seen.Add(num);
        }
        return -1;
    }
}

func findDuplicate(nums []int) int {
    seen := make(map[int]struct{})
    for _, num := range nums {
        if _, exists := seen[num]; exists {
            return num
        }
        seen[num] = struct{}{}
    }
    return -1
}

class Solution {
    fun findDuplicate(nums: IntArray): Int {
        val seen = HashSet<Int>()
        for (num in nums) {
            if (num in seen) {
                return num
            }
            seen.add(num)
        }
        return -1
    }
}

class Solution {
    func findDuplicate(_ nums: [Int]) -> Int {
        var seen = Set<Int>()
        for num in nums {
            if seen.contains(num) {
                return num
            }
            seen.insert(num)
        }
        return -1
    }
}

impl Solution {
    pub fn find_duplicate(nums: Vec<i32>) -> i32 {
        let mut seen = HashSet::new();
        for num in nums {
            if seen.contains(&num) {
                return num;
            }
            seen.insert(num);
        }
        -1
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Array

Intuition

Since the values in the array are from 1 to n, we can use an array to track whether we've seen a number before.
Each number directly maps to an index (num - 1).

If that index is already marked, we've seen the number before → it's the duplicate.
Otherwise, we mark it as seen.

This avoids using a hash set while still providing fast lookups.

Algorithm

Create an array seen of size n filled with zeros.
For each number num in the input array:
- Check if seen[num - 1] is already set to 1.
  - If yes, return num (duplicate found).
- Otherwise, set seen[num - 1] = 1.
Return -1 if no duplicate is found (though the problem guarantees one).

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        seen = [0] * len(nums)
        for num in nums:
            if seen[num - 1]:
                return num
            seen[num - 1] = 1
        return -1

public class Solution {
    public int findDuplicate(int[] nums) {
        int[] seen = new int[nums.length];
        for (int num : nums) {
            if (seen[num - 1] == 1) {
                return num;
            }
            seen[num - 1] = 1;
        }
        return -1;
    }
}

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        vector<int> seen(nums.size(), 0);
        for (int num : nums) {
            if (seen[num - 1] == 1) {
                return num;
            }
            seen[num - 1] = 1;
        }
        return -1;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    findDuplicate(nums) {
        let seen = new Array(nums.length).fill(0);
        for (let num of nums) {
            if (seen[num - 1]) {
                return num;
            }
            seen[num - 1] = 1;
        }
        return -1;
    }
}

public class Solution {
    public int FindDuplicate(int[] nums) {
        int[] seen = new int[nums.Length];
        foreach (int num in nums) {
            if (seen[num - 1] == 1) {
                return num;
            }
            seen[num - 1] = 1;
        }
        return -1;
    }
}

func findDuplicate(nums []int) int {
    seen := make([]int, len(nums))
    for _, num := range nums {
        if seen[num-1] == 1 {
            return num
        }
        seen[num-1] = 1
    }
    return -1
}

class Solution {
    fun findDuplicate(nums: IntArray): Int {
        val seen = IntArray(nums.size)
        for (num in nums) {
            if (seen[num - 1] == 1) {
                return num
            }
            seen[num - 1] = 1
        }
        return -1
    }
}

class Solution {
    func findDuplicate(_ nums: [Int]) -> Int {
        var seen = [Int](repeating: 0, count: nums.count)
        for num in nums {
            if seen[num - 1] == 1 {
                return num
            }
            seen[num - 1] = 1
        }
        return -1
    }
}

impl Solution {
    pub fn find_duplicate(nums: Vec<i32>) -> i32 {
        let mut seen = vec![0; nums.len()];
        for num in nums {
            if seen[(num - 1) as usize] == 1 {
                return num;
            }
            seen[(num - 1) as usize] = 1;
        }
        -1
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Negative Marking

Intuition

Since every value is between 1 and n, each number corresponds to an index in the array (num - 1).
We can use the array itself as a marking tool:

When we see a number, we go to its corresponding index and flip the sign of the value there.
If we ever visit an index that is already negative, it means we've visited this number before → it's the duplicate.

This method avoids extra memory and uses the input array as a tracking structure.

Algorithm

Loop through every number num in the array.
Compute its corresponding index: idx = abs(num) - 1.
If nums[idx] is already negative:
- A duplicate has been found, return abs(num).
Otherwise:
- Mark the index by multiplying nums[idx] by -1.
If no duplicate is found (though guaranteed), return -1.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        for num in nums :
            idx = abs(num) - 1
            if nums[idx] < 0 :
                return abs(num)
            nums[idx] *= -1
        return -1

public class Solution {
    public int findDuplicate(int[] nums) {
        for (int num : nums) {
            int idx = Math.abs(num) - 1;
            if (nums[idx] < 0) {
                return Math.abs(num);
            }
            nums[idx] *= -1;
        }
        return -1;
    }
}

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        for (int num : nums) {
            int idx = abs(num) - 1;
            if (nums[idx] < 0) {
                return abs(num);
            }
            nums[idx] *= -1;
        }
        return -1;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    findDuplicate(nums) {
        for (let num of nums) {
            let idx = Math.abs(num) - 1;
            if (nums[idx] < 0) {
                return Math.abs(num);
            }
            nums[idx] *= -1;
        }
        return -1;
    }
}

public class Solution {
    public int FindDuplicate(int[] nums) {
        foreach (int num in nums) {
            int idx = Math.Abs(num) - 1;
            if (nums[idx] < 0) {
                return Math.Abs(num);
            }
            nums[idx] *= -1;
        }
        return -1;
    }
}

func findDuplicate(nums []int) int {
    for _, num := range nums {
        idx := abs(num) - 1
        if nums[idx] < 0 {
            return abs(num)
        }
        nums[idx] *= -1
    }
    return -1
}

func abs(num int) int {
    if num < 0 {
        return -num
    }
    return num
}

class Solution {
    fun findDuplicate(nums: IntArray): Int {
        for (num in nums) {
            val idx = Math.abs(num) - 1
            if (nums[idx] < 0) {
                return Math.abs(num)
            }
            nums[idx] *= -1
        }
        return -1
    }
}

class Solution {
    func findDuplicate(_ nums: [Int]) -> Int {
        var nums = nums
        for num in nums {
            let idx = abs(num) - 1
            if nums[idx] < 0 {
                return abs(num)
            }
            nums[idx] *= -1
        }
        return -1
    }
}

impl Solution {
    pub fn find_duplicate(mut nums: Vec<i32>) -> i32 {
        for i in 0..nums.len() {
            let idx = (nums[i].abs() - 1) as usize;
            if nums[idx] < 0 {
                return nums[i].abs();
            }
            nums[idx] *= -1;
        }
        -1
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

5. Binary Search

Intuition

This method uses binary search on the value range, not on the array itself.

If all numbers from 1 to mid appeared at most once, then the count of numbers <= mid should be <= mid.
But if the count is greater than mid, it means the duplicate must be in the range [1, mid], because too many numbers fall into that range.

So we repeatedly:

Count how many values are <= mid.
Shrink the search space based on whether this count is "too large."

Eventually, low == high, and that value is the duplicate.

Algorithm

Let low = 1 and high = n - 1 (value range).
While low < high:
- Compute mid = (low + high) // 2.
- Count how many numbers in the array are <= mid.
- If the count is greater than mid, the duplicate lies in [low, mid], so set high = mid.
- Otherwise, it lies in [mid + 1, high], so set low = mid + 1.
When the loop ends, low is the duplicate.
Return low.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        low, high = 1, n - 1
        while low < high:
            mid = low + (high - low) // 2
            lessOrEqual = sum(1 for num in nums if num <= mid)

            if lessOrEqual <= mid:
                low = mid + 1
            else:
                high = mid

        return low

public class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int low = 1;
        int high = n - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            int lessOrEqual = 0;
            for (int i = 0; i < n; i++) {
                if (nums[i] <= mid) {
                    lessOrEqual++;
                }
            }

            if (lessOrEqual <= mid) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low;
    }
}

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int low = 1, high = n - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            int lessOrEqual = 0;
            for (int i = 0; i < n; i++) {
                if (nums[i] <= mid) {
                    lessOrEqual++;
                }
            }

            if (lessOrEqual <= mid) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    findDuplicate(nums) {
        let n = nums.length;
        let low = 1,
            high = n - 1;

        while (low < high) {
            let mid = Math.floor(low + (high - low) / 2);
            let lessOrEqual = 0;

            for (let i = 0; i < n; i++) {
                if (nums[i] <= mid) {
                    lessOrEqual++;
                }
            }

            if (lessOrEqual <= mid) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low;
    }
}

public class Solution {
    public int FindDuplicate(int[] nums) {
        int n = nums.Length;
        int low = 1, high = n - 1;

        while (low < high) {
            int mid = low + (high - low) / 2;
            int lessOrEqual = 0;

            for (int i = 0; i < n; i++) {
                if (nums[i] <= mid) {
                    lessOrEqual++;
                }
            }

            if (lessOrEqual <= mid) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low;
    }
}

func findDuplicate(nums []int) int {
    n := len(nums)
    low, high := 1, n-1

    for low < high {
        mid := low + (high-low)/2
        lessOrEqual := 0

        for _, num := range nums {
            if num <= mid {
                lessOrEqual++
            }
        }

        if lessOrEqual <= mid {
            low = mid + 1
        } else {
            high = mid
        }
    }

    return low
}

class Solution {
    fun findDuplicate(nums: IntArray): Int {
        val n = nums.size
        var low = 1
        var high = n - 1

        while (low < high) {
            val mid = low + (high - low) / 2
            var lessOrEqual = 0

            for (num in nums) {
                if (num <= mid) {
                    lessOrEqual++
                }
            }

            if (lessOrEqual <= mid) {
                low = mid + 1
            } else {
                high = mid
            }
        }

        return low
    }
}

class Solution {
    func findDuplicate(_ nums: [Int]) -> Int {
        let n = nums.count
        var low = 1, high = n - 1

        while low < high {
            let mid = low + (high - low) / 2
            let lessOrEqual = nums.filter { $0 <= mid }.count

            if lessOrEqual <= mid {
                low = mid + 1
            } else {
                high = mid
            }
        }
        return low
    }
}

impl Solution {
    pub fn find_duplicate(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let (mut low, mut high) = (1i32, (n - 1) as i32);
        while low < high {
            let mid = low + (high - low) / 2;
            let less_or_equal = nums.iter().filter(|&&x| x <= mid).count();
            if less_or_equal as i32 <= mid {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        low
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$

6. Bit Manipulation

Intuition

Every number from 1 to n−1 should appear exactly once, but in the array, one number appears twice.
So for each bit position, we compare:

How many times this bit is set among all numbers in the array.
How many times this bit should be set among the numbers 1 to n-1.

If a bit appears more times in the array than expected, that bit must belong to the duplicate number.

By combining all such bits, we reconstruct the duplicate.

Algorithm

Let res = 0 to build the duplicate number bit by bit.
For each bit position b from 0 to 31:
- Compute mask = 1 << b.
- Count how many numbers in nums have this bit set, call it x.
- Count how many numbers from 1 to n - 1 should have this bit set, call it y.
If x > y, it means the duplicate has this bit set, so add it to the answer:
- res |= mask.
After processing all bits, return res.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        for b in range(32):
            x = y = 0
            mask = 1 << b
            for num in nums:
                if num & mask:
                    x += 1

            for num in range(1, n):
                if num & mask:
                    y += 1

            if x > y:
                res |= mask
        return res

public class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int b = 0; b < 32; b++) {
            int x = 0, y = 0;
            int mask = 1 << b;
            for (int num : nums) {
                if ((num & mask) != 0) {
                    x++;
                }
            }
            for (int num = 1; num < n; num++) {
                if ((num & mask) != 0) {
                    y++;
                }
            }
            if (x > y) {
                res |= mask;
            }
        }
        return res;
    }
}

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        for (int b = 0; b < 32; b++) {
            int x = 0, y = 0;
            int mask = 1 << b;
            for (int num : nums) {
                if (num & mask) {
                    x++;
                }
            }
            for (int num = 1; num < n; num++) {
                if (num & mask) {
                    y++;
                }
            }
            if (x > y) {
                res |= mask;
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    findDuplicate(nums) {
        let n = nums.length;
        let res = 0;
        for (let b = 0; b < 32; b++) {
            let x = 0,
                y = 0;
            let mask = 1 << b;
            for (let num of nums) {
                if (num & mask) {
                    x++;
                }
            }
            for (let num = 1; num < n; num++) {
                if (num & mask) {
                    y++;
                }
            }
            if (x > y) {
                res |= mask;
            }
        }
        return res;
    }
}

public class Solution {
    public int FindDuplicate(IList<int> nums) {
        int n = nums.Count;
        int res = 0;
        for (int b = 0; b < 32; b++) {
            int x = 0, y = 0;
            int mask = 1 << b;
            foreach (int num in nums) {
                if ((num & mask) != 0) {
                    x++;
                }
            }
            for (int num = 1; num < n; num++) {
                if ((num & mask) != 0) {
                    y++;
                }
            }
            if (x > y) {
                res |= mask;
            }
        }
        return res;
    }
}

func findDuplicate(nums []int) int {
    n := len(nums)
    res := 0

    for b := 0; b < 32; b++ {
        x, y := 0, 0
        mask := 1 << b

        for _, num := range nums {
            if num&mask != 0 {
                x++
            }
        }

        for num := 1; num < n; num++ {
            if num&mask != 0 {
                y++
            }
        }

        if x > y {
            res |= mask
        }
    }

    return res
}

class Solution {
    fun findDuplicate(nums: IntArray): Int {
        val n = nums.size
        var res = 0

        for (b in 0 until 32) {
            var x = 0
            var y = 0
            val mask = 1 shl b

            for (num in nums) {
                if (num and mask != 0) {
                    x++
                }
            }

            for (num in 1 until n) {
                if (num and mask != 0) {
                    y++
                }
            }

            if (x > y) {
                res = res or mask
            }
        }

        return res
    }
}

class Solution {
    func findDuplicate(_ nums: [Int]) -> Int {
        let n = nums.count
        var res = 0

        for b in 0..<32 {
            var x = 0, y = 0
            let mask = 1 << b

            for num in nums {
                if num & mask != 0 {
                    x += 1
                }
            }

            for num in 1..<n {
                if num & mask != 0 {
                    y += 1
                }
            }

            if x > y {
                res |= mask
            }
        }
        return res
    }
}

impl Solution {
    pub fn find_duplicate(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        let mut res = 0;
        for b in 0..32 {
            let mask = 1 << b;
            let mut x = 0;
            let mut y = 0;
            for &num in &nums {
                if num & mask != 0 {
                    x += 1;
                }
            }
            for num in 1..n {
                if num & mask != 0 {
                    y += 1;
                }
            }
            if x > y {
                res |= mask;
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(32 * n)$
Space complexity: $O(1)$

7. Fast And Slow Pointers

Intuition

Treat the array like a linked list, where each index points to the next index given by its value.
Because one number is duplicated, two indices will point into the same chain, creating a cycle — exactly like a linked list with a loop.

Using Floyd’s Fast & Slow Pointer technique:

The slow pointer moves one step at a time.
The fast pointer moves two steps at a time.
If there’s a cycle, they will eventually meet.

Once they meet, we start a new pointer from the beginning:

Move both pointers one step at a time.
The point where they meet again is the duplicate number (the entry point of the cycle).

Algorithm

Initialize two pointers slow = 0 and fast = 0.
Move:
- slow = nums[slow]
- fast = nums[nums[fast]]
  until slow == fast.
Start a new pointer slow2 = 0.
Move both:
- slow = nums[slow]
- slow2 = nums[slow2]
  until they meet.
The meeting point is the duplicate number.
Return that number.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        slow2 = 0
        while True:
            slow = nums[slow]
            slow2 = nums[slow2]
            if slow == slow2:
                return slow

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                break;
            }
        }

        int slow2 = 0;
        while (true) {
            slow = nums[slow];
            slow2 = nums[slow2];
            if (slow == slow2) {
                return slow;
            }
        }
    }
}

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                break;
            }
        }

        int slow2 = 0;
        while (true) {
            slow = nums[slow];
            slow2 = nums[slow2];
            if (slow == slow2) {
                return slow;
            }
        }
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    findDuplicate(nums) {
        let slow = 0;
        let fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow === fast) {
                break;
            }
        }

        let slow2 = 0;
        while (true) {
            slow = nums[slow];
            slow2 = nums[slow2];
            if (slow === slow2) {
                return slow;
            }
        }
    }
}

public class Solution {
    public int FindDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                break;
            }
        }

        int slow2 = 0;
        while (true) {
            slow = nums[slow];
            slow2 = nums[slow2];
            if (slow == slow2) {
                return slow;
            }
        }
    }
}

func findDuplicate(nums []int) int {
    slow, fast := 0, 0

    for {
        slow = nums[slow]
        fast = nums[nums[fast]]

        if slow == fast {
            break
        }
    }

    slow2 := 0
    for {
        slow = nums[slow]
        slow2 = nums[slow2]

        if slow == slow2 {
            return slow
        }
    }
}

class Solution {
    fun findDuplicate(nums: IntArray): Int {
        var slow = 0
        var fast = 0

        while (true) {
            slow = nums[slow]
            fast = nums[nums[fast]]

            if (slow == fast) {
                break
            }
        }

        var slow2 = 0
        while (true) {
            slow = nums[slow]
            slow2 = nums[slow2]

            if (slow == slow2) {
                return slow
            }
        }
    }
}

class Solution {
    func findDuplicate(_ nums: [Int]) -> Int {
        var slow = 0, fast = 0

        while true {
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast {
                break
            }
        }

        var slow2 = 0
        while true {
            slow = nums[slow]
            slow2 = nums[slow2]
            if slow == slow2 {
                return slow
            }
        }
    }
}

impl Solution {
    pub fn find_duplicate(nums: Vec<i32>) -> i32 {
        let mut slow = 0usize;
        let mut fast = 0usize;
        loop {
            slow = nums[slow] as usize;
            fast = nums[nums[fast] as usize] as usize;
            if slow == fast {
                break;
            }
        }

        let mut slow2 = 0usize;
        loop {
            slow = nums[slow] as usize;
            slow2 = nums[slow2] as usize;
            if slow == slow2 {
                return slow as i32;
            }
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Modifying the Array When Not Allowed

Some problem variants require not modifying the input array. Solutions like negative marking or in-place sorting alter the original data. Always check the constraints before choosing an approach that mutates the input.

Off-by-One Errors in Index Mapping

Since values range from 1 to n but array indices start at 0, forgetting to subtract 1 when mapping values to indices causes out-of-bounds errors or incorrect results. For example, value n maps to index n-1, not index n.

Misunderstanding Floyd's Cycle Detection Entry Point

In the fast and slow pointer approach, the meeting point of the two pointers is not the duplicate number. After they meet, you must start a new pointer from index 0 and move both pointers one step at a time until they meet again. This second meeting point is the cycle entry, which corresponds to the duplicate value.