Find the Duplicate Number

Time

O (n)

Space

O (1)

Problem

LeetCodeOpen original problem

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.

You must solve the problem without modifying the array nums and uses only constant extra space.

Solution approach

Intuition

Treat the array as a function: from index i we move to index nums[i]. All values lie in [1, n], so starting at index 0 we can follow this forever. Since two different indices point to the duplicate value, that value has two incoming arrows, and it is exactly the entrance of the cycle we eventually fall into. Floyd’s tortoise-and-hare method finds a cycle entrance in $O(n)$ time without extra memory and without modifying the array.

Algorithm

Start from index 0: slow = nums[0] (one step) and fast = nums[nums[0]] (two steps).
Move slow one step and fast two steps until they meet inside the cycle.
Reset fast = 0. Now move both one step at a time; the point where they meet is the cycle entrance.
Return slow, the duplicate value. If nums.size() is 1 or less, return -1.

Complexity

Time: $O(n)$ — both phases take at most a linear number of steps.
Space: $O(1)$ — only two pointers.

Edge cases

Duplicate appearing many times (e.g. [2, 2, 2, 2]): it is still the only value with several incoming arrows, so it is still the cycle entrance.

Code

1
class Solution {
2
   public:
3
    int findDuplicate(vector<int>& nums) {
4
        if (nums.size() > 1) {
5
            int slow = nums[0];
6
            int fast = nums[nums[0]];
7
            while (slow != fast) {
8
                slow = nums[slow];
9
                fast = nums[nums[fast]];
10
            }
11

12
            fast = 0;
13
            while (fast != slow) {
14
                fast = nums[fast];
15
                slow = nums[slow];
16
            }
17
            return slow;
18
        }
19
        return -1;
20
    }
21
};

Give it a try first

Attempt the problem on LeetCode — the code will still be here.