Find the Duplicate Number — Editorial

Opening the reading…

Intuitionthe repeated value becomes a cycle entrance

Use each array position as a node and nums[i] as the next pointer from that node. Starting at index 0, repeatedly moving to nums[current] creates a linked-list-like walk. Every value is between 1 and n, so after the first move the walk stays among valid indices; it can never run out of bounds.

There are n + 1 positions but only n possible next values. The duplicate value gives two different positions the same outgoing destination, which causes two paths to merge. Once paths merge, the walk eventually repeats a node and forms a cycle. The first repeated node is not necessarily the duplicate itself, but the entrance to that cycle is exactly the duplicate value.

The duplicate creates the merge that makes a cycle.

Approach

Start slow and fast at nums[0], because index 0 is only a safe entry point into the value-defined walk and is not itself a candidate duplicate.

Move slow by one next pointer and fast by two next pointers inside a do-while loop, because checking before the first move would make both pointers equal immediately and skip cycle detection.

Stop when slow and fast meet inside the cycle, because a one-step and a two-step walker must eventually coincide once both are circulating through the same finite cycle.

Reset slow to nums[0] while leaving fast at the meeting point, because the distance from the start to the cycle entrance matches the appropriate distance from the meeting point around the cycle.

Move both pointers one step at a time until they meet again, because equal-speed walkers starting at those positions meet exactly at the cycle entrance.

Return the meeting value, because the cycle entrance is the array value reached by the duplicate number of positions.

Complexityconstant working memory despite the cycle

MEASURE	BOUND	WHY
Time	O(n)	Each phase follows the functional graph for at most a linear number of steps before meeting. The first phase stays within the cycle, and the second advances toward its entrance, so no phase can revisit an unbounded number of distinct positions.
Space	O(1) extra	Only slow and fast are stored; the input array is not modified, and the returned integer is output rather than working memory. The bound remains constant whether the cycle is short, long, or nearly all n values.

Here n is the largest possible value and nums has length n + 1.

Annotated solutionC++ · Floyd's two-phase cycle detection

CPPFloyd's algorithm first finds any point inside the cycle, then finds the cycle entrance.

#include <vector>
using namespace std;

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

The counting alternativea valid binary-search solution with a time-space tradeoff

You can also binary search the value range from 1 to n rather than walking pointers. For a midpoint mid, count how many array values are less than or equal to mid. If that count is greater than mid, the duplicate must be in 1 to mid by the pigeonhole principle; otherwise it must be in mid + 1 to n. This is a different arrangement, not an optimisation: it keeps constant space but takes O(n log n) time.

CPPBinary search on the value range, counting values at most mid.

#include <vector>
using namespace std;

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int left = 1;
        int right = static_cast<int>(nums.size()) - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = 0;

            for (int value : nums) {
                if (value <= mid) {
                    ++count;
                }
            }

            if (count > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
};

The count compares the number of entries that belong to the lower value range with the number of distinct values that range can contain. A count above mid means that range contains a repetition, so discarding it would discard the answer. The scan does not alter nums, and the search range halves after each scan, giving O(n log n) time and O(1) extra space.