287 - Find the Duplicate Number

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 use only constant extra space.

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

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

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

Constraints:

• 1 <= n <= 10^5
• 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

Approach

nums = [1, 3, 4, 2, 2]
i:      0  1  2  3  4

following i -> nums[i] from 0:

0 -> 1 -> 3 -> 2 -> 4
               ^    |
               +----+

tail      0 -> 1 -> 3
cycle     2 -> 4 -> 2
entrance  2, which is the duplicate

nums[4] is 2 and nums[2] is 4, so the loop is just those two. Node 3 sits on the tail, not in the cycle — it is the last node before the entrance, which is a different thing and the easy one to mislabel when sketching these.

Floyd’s Cycle Detection

• Phase one: finds some node in the cycle. Move s one step per iteration and f two. Once both are inside the cycle the gap closes by one each step, so they must land on the same node.
• Phase two: converts that into the entrance. Reset s to the head and advance both one step at a time; they meet again exactly at the cycle’s start.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int s = 0, f = 0;
        do {
            s = nums[s];
            f = nums[nums[f]];
        } while (s != f);

        s = 0;
        while (s != f) {
            s = nums[s];
            f = nums[f];
        }
        return s;
    }
};

• time: O(n) — phase one is at most a + c iterations, phase two at most a
• space: O(1) — two indices, and the array is never written to

Cyclic Sort

Every value is in [1, n], so value v has a home at index v - 1. Walk the array and keep swapping the current value to its home until the slot already holds its own value, then move on. When the placing finishes, every index holds its matching value except where the duplicate forced a collision, so one scan finds it.

int findDuplicate(vector<int>& nums) {
    const int n = nums.size();
    int i = 1;
    while (i <= n) {
        int corr = nums[i - 1];
        if (nums[corr - 1] != corr) {
            swap(nums[corr - 1], nums[i - 1]);
        } else {
            i++;
        }
    }
    for (int j = 1; j <= n; j++)
        if (nums[j - 1] != j) return nums[j - 1];
    return -1;
}