0287. Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1,1]
Output: 1

Example 4:

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

Constraints:

• 2 <= n <= 3 * 104
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem without modifying the array nums?
• Can you solve the problem using only constant, O(1) extra space?
• Can you solve the problem with runtime complexity less than O(n2)?

Analysis

We can think about this problem as similar to linked list cycle II. For each element in the array: i has an edge to nums[i]. If we find a cycle, that means there are two indexes pointing to the same element from the array.

For example, nums = [1,3,4,2,2], using a graph, it can be represented as:

There is one and only one node with an in-degree of two, which makes the "linked list" a cycle, and our task is to find the one with an in-degree of two.

1. using two pointers to get into the cycle: one pointer moves by one step each time, the other moves by two steps.

2. reset one of the pointers to 0, so that it's outside the cycle, keep moving the other pointer and the current one until they meet. The only node that these two pointers will meet is the one with an in-degree of 2.

3. Time: $O(2 \times n)$

4. Space: $O(1)$

Code

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int a = 0, b = 0;
        do { // do while since 0 == 0 is our initial condition
            a = nums[nums[a]];
            b = nums[b];
        }  while (a != b) ;
        a = 0;
        while (a != b) {
            a = nums[a];
            b = nums[b];
        }
        return a;
    }
};