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 without modifying the array and using only constant extra space.

Examples

The brute-force approach

Sort the array and check adjacent elements for equality. Or use a hash set to track seen values.

# Hash set approach
seen = set()
for n in nums:
    if n in seen: return n
    seen.add(n)

O(n) time but O(n) space for the hash set. Sorting works in O(n log n) but modifies the array, which is forbidden.

Spotting the pattern

This is a Fast and Slow Pointers problem. The key question to ask yourself:

If nums = [1,3,4,2,2], starting at index 0: 0 → 1 → 3 → 2 → 4 → 2 → 4... Where does the cycle start, and what does that position represent?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.