Find the Duplicate Number

NeetCode: Find the Duplicate Number · LeetCode: 287. Find the Duplicate Number · Difficulty: Medium

An array nums has n + 1 integers, each in 1..n, and exactly one value repeats (possibly more than twice). Return the repeated value without modifying the array, using O(1) extra space.

Example

Text

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

Brute force: HashSet

HashSet.add returns false when the value is already present, so the first failed add is the duplicate. The -1 after the loop is never reached for valid input.

Java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            if (!seen.add(x)) {
                return x;
            }
        }
        return -1; // unreachable: the input always has a duplicate
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findDuplicate(new int[]{1, 2, 3, 2, 2}));
        System.out.println(s.findDuplicate(new int[]{1, 2, 3, 4, 4}));
    }
}

Output

2
4

Time: O(n). Space: O(n), which breaks the space requirement. Sorting a copy also needs O(n) space, and sorting in place modifies the input.

Optimal: Floyd's cycle detection on the array

Treat the array as a linked list where index i points to index nums[i]. Every value is in 1..n, so no pointer leads back to index 0, which makes index 0 the start and keeps every step inside the array. Because two indices hold the same value, two nodes point to the same next node: that node is the entry of a cycle, and its value is the duplicate.

Move slow by one and fast by two until they meet inside the cycle.
Start a second pointer from index 0. Move it and slow one step at a time; they meet exactly at the cycle entry.

Java

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        int start = 0;
        while (start != slow) {
            start = nums[start];
            slow = nums[slow];
        }
        return start;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findDuplicate(new int[]{1, 2, 3, 2, 2}));
        System.out.println(s.findDuplicate(new int[]{1, 2, 3, 4, 4}));
        System.out.println(s.findDuplicate(new int[]{3, 1, 3, 4, 2}));
    }
}

Output

2
4
3

Time: O(n). Space: O(1).