287. Find the Duplicate Number (Medium)

Problem

Given an array nums of n + 1 integers where each value is in the range [1, n], there is exactly one number that appears two or more times. Find that number.

Constraints:

• You must not modify the array.
• You must use only constant extra space.
• The runtime must be less than $O(n²)$.

Example

• nums = [1,3,4,2,2] → 2
• nums = [3,1,3,4,2] → 3
• nums = [3,3,3,3,3] → 3

LeetCode 287 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, sort

Sort the array; the duplicate sits next to one of its copies.

Python

def find_duplicate(nums):
    nums_sorted = sorted(nums)                    # L1: O(n log n) sort
    for i in range(1, len(nums_sorted)):
        if nums_sorted[i] == nums_sorted[i - 1]:  # L2: O(1) compare adjacent
            return nums_sorted[i]
    return -1

TypeScript

function findDuplicate(nums: number[]): number {
    const sorted = [...nums].sort((a, b) => a - b);  // L1: O(n log n) sort
    for (let i = 1; i < sorted.length; i++) {
        if (sorted[i] === sorted[i - 1]) return sorted[i];  // L2: O(1) compare adjacent
    }
    return -1;
}

Swift

final class Solution {
func findDuplicate(_ nums: [Int]) -> Int {
        let sorted = nums.sorted()
        for index in 1..<sorted.count where sorted[index] == sorted[index - 1] {
            return sorted[index]
        }
        return -1
    }
}

Where the time goes, line by line

Variables: n = length of nums (n + 1 integers in range [1, n]).

Line	Per-call cost	Times executed	Contribution
L1 (sort)	$O(n log n)$	1	$O(n log n)$ ← dominates
L2 (scan adjacent)	$O(1)$	up to n	$O(n)$

Sorting is the only superlinear step. The scan at L2 is $O(n)$ but dominated by L1.

Complexity

• Time: $O(n log n)$, driven by L1.
• Space: $O(n)$ (Python sort copies).

Violates “don’t modify” in spirit (we’re using a sorted copy, but the problem usually permits non-destructive). Fails the $O(1)$ space constraint.

Approach 2: Hash set

Walk once, checking a set.

Python

def find_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:          # L1: O(1) set lookup
            return x
        seen.add(x)            # L2: O(1) set insert
    return -1

TypeScript

function findDuplicate(nums: number[]): number {
    const seen = new Set<number>();
    for (const x of nums) {
        if (seen.has(x)) return x;  // L1: O(1) set lookup
        seen.add(x);                // L2: O(1) set insert
    }
    return -1;
}

Swift

final class Solution {
func findDuplicate(_ nums: [Int]) -> Int {
        var seen: Set<Int> = []
        for value in nums {
            guard seen.insert(value).inserted else { return value }
        }
        return -1
    }
}

Where the time goes, line by line

Variables: n = length of nums (n + 1 integers in range [1, n]).

Line	Per-call cost	Times executed	Contribution
L1 (set lookup)	$O(1)$	up to n + 1	$O(n)$ ← dominates
L2 (set insert)	$O(1)$	up to n	$O(n)$

We return as soon as the duplicate is found, so at most n + 1 iterations.

Complexity

• Time: $O(n)$, driven by L1/L2.
• Space: $O(n)$.

Fails the $O(1)$ space constraint.

Approach 3: Floyd’s cycle detection on array-as-linked-list (optimal)

Treat i → nums[i] as a linked-list transition. With values in [1, n] and an array of length n + 1, a duplicate value creates a cycle in this implicit linked list. The entry of the cycle is the duplicate.

Standard Floyd’s: phase 1 finds a point inside the cycle; phase 2 resets one pointer to the start and walks both by one, they meet at the cycle entrance.

Python

def find_duplicate(nums):
    # Phase 1: find meeting point inside the cycle
    slow = nums[0]
    fast = nums[0]
    while True:
        slow = nums[slow]          # L1: O(1) slow advances 1 step
        fast = nums[nums[fast]]    # L2: O(1) fast advances 2 steps
        if slow == fast:
            break
    # Phase 2: find the entrance of the cycle
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]          # L3: O(1) slow advances 1 step
        fast = nums[fast]          # L4: O(1) fast advances 1 step
    return slow

TypeScript

function findDuplicate(nums: number[]): number {
    // Phase 1: find meeting point inside the cycle
    let slow = nums[0];
    let fast = nums[0];
    do {
        slow = nums[slow];         // L1: O(1) slow advances 1 step
        fast = nums[nums[fast]];   // L2: O(1) fast advances 2 steps
    } while (slow !== fast);
    // Phase 2: find the entrance of the cycle
    slow = nums[0];
    while (slow !== fast) {
        slow = nums[slow];         // L3: O(1) slow advances 1 step
        fast = nums[fast];         // L4: O(1) fast advances 1 step
    }
    return slow;
}

Swift

final class Solution {
func findDuplicate(_ nums: [Int]) -> Int {
        var slow = nums[0]
        var fast = nums[0]
        repeat {
            slow = nums[slow]
            fast = nums[nums[fast]]
        } while slow != fast
        slow = nums[0]
        while slow != fast {
            slow = nums[slow]
            fast = nums[fast]
        }
        return slow
    }
}

Where the time goes, line by line

Variables: n = length of nums minus 1 (values in range [1, n], array length n + 1).

Line	Per-call cost	Times executed	Contribution
L1-L2 (phase 1)	$O(1)$	up to n + cycle length	$O(n)$ ← dominates phase 1
L3-L4 (phase 2)	$O(1)$	up to n	$O(n)$ ← dominates phase 2

Phase 1 detects the cycle in $O(n + c)$ steps where c is the cycle length. Phase 2 walks at most n steps to reach the cycle entrance. Total: $O(n)$.

Complexity

• Time: $O(n)$, driven by L1-L2 (phase 1) and L3-L4 (phase 2).
• Space: $O(1)$.

Why array-as-linked-list works

nums[i] is in [1, n], so it’s always a valid next index. Starting from index 0, you can’t revisit 0 (since no nums[i] == 0), so any cycle you encounter must begin at the duplicate value, every other value has exactly one predecessor.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_287.py and run.
# Uses Floyd's cycle detection approach (Approach 3).

def find_duplicate(nums):
    slow = nums[0]
    fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

def _run_tests():
    # Examples from problem statement
    assert find_duplicate([1,3,4,2,2]) == 2
    assert find_duplicate([3,1,3,4,2]) == 3
    # All same value
    assert find_duplicate([3,3,3,3,3]) == 3
    # Duplicate at boundary
    assert find_duplicate([1,1]) == 1
    assert find_duplicate([2,2,2,1]) == 2
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function findDuplicate(nums: number[]): number {
    let slow = nums[0], 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;
}

console.assert(findDuplicate([1,3,4,2,2]) === 2);
console.assert(findDuplicate([3,1,3,4,2]) === 3);
console.assert(findDuplicate([3,3,3,3,3]) === 3);
console.assert(findDuplicate([1,1]) === 1);
console.assert(findDuplicate([2,2,2,1]) === 2);
console.log("all tests pass");

Summary

Approach	Time	Space	Meets constraints?
Sort	$O(n log n)$	$O(n)$	No
Hash set	$O(n)$	$O(n)$	No
Floyd’s on array-as-list	$O(n)$	$O(1)$	Yes

This is a classic “looks like an array problem, solved with a linked-list algorithm” puzzle. Recognizing the array-as-linked-list framing is the key.

Related data structures

• Arrays, input; indexed as implicit linked list
• Linked Lists, Floyd’s tortoise and hare

Related concepts

• Fast and Slow Pointers, the pointer speed trick for finding middles, cycles, and distance from the end.
• Cycle Detection, the repeated state pattern for proving loops in lists, graphs, or processes.