DSA SheetMedium
EditorialPractice

SORTING › CYCLIC SORT

Find the Duplicate Number

MediumEditorial · 8 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

An array represented as a linked list with a cycleDraw nodes labelled 0 and the values 1 through n as a directed linked list. An arrow from each node i points to the node labelled nums[i]. The path from node 0 eventually reaches a node labelled with the duplicate value. Two different incoming arrows meet at that node, and arrows from there form a loop back to it. The meeting point of the two paths is the cycle entrance, which is the duplicate number.value 3nums[3] → 4value 4nums[4] →2value 2nums[2] →3value 1nums[1] → 131342nums[0]nums[2]array nums01234two array positions point to 3cycle: 3 → 4 → 2 → 3
The duplicate creates the merge that makes a cycle.

Approach

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(1) extraOnly 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.

Common mistakesspecific ways the cycle argument gets lost

Previous · Missing Number