Skip to content

Volume ITechnology

4.9.8 — Find the Duplicate Number ​

LeetCode 287 · Medium

The problem ​

You are given a list nums of n + 1 whole numbers. Every number is between 1 and n. Exactly one value is repeated, and it may appear two or more times. Return that value.

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

n can be up to 100,000. Two rules make this hard. You may not change the list, and you may use only O(1) extra memory.

What the problem is really asking ​

First, why must a repeat exist? There are n + 1 slots, but only n possible values, 1 to n. If every slot held a different value, you would need n + 1 different values. You only have n. So at least two slots share a value. This is called the pigeonhole principle: if you put more pigeons than holes, some hole holds two pigeons.

Now look at the rules. Every obvious method is banned.

  • A set of seen values uses O(n) memory. Banned.
  • Sorting, then comparing neighbours changes the list. Banned.
  • Marking seen values by making nums[x] negative changes the list. Banned.

When a problem forbids every obvious method, the rules are a hint. Ask what is left. Here, almost nothing is, which is why the intended answer is surprising.

The brute force, and where it wastes work ​

Compare every pair. It uses no extra memory and does not change the list.

python
def findDuplicate(nums):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return nums[i]

But it is O(n^2), about five billion comparisons for 100,000 numbers.

The waste in one sentence: it compares values blindly, when the values themselves are valid positions in the list and can be followed like pointers.

The idea ​

Treat the list as a set of signposts. From position i, the signpost says "go to position nums[i]".

That is always allowed. Every value is between 1 and n, and the list has positions 0 to n, so every value is a real position. Each position has exactly one signpost, so each position leads to exactly one next position. That is a linked list, built inside a plain list, with no pointers at all.

Now the key facts.

  1. Start at position 0. No value is 0, so no signpost ever leads into position 0. That makes it a safe place to start, outside any loop.
  2. The walk must enter a cycle. There are only n + 1 positions, so the walk must eventually revisit one.
  3. The repeated value is the entrance to the cycle. Two different positions hold the repeated value, so two different signposts point to the same position. That position is where two paths merge, and in a "one next step" structure, the point where paths merge is the start of the cycle.
nums = [1, 3, 4, 2, 2]
position:  0 → 1 → 3 → 2 → 4 → 2 → 4 → ...
                       ↑_______|

positions 3 and 4 both hold the value 2, so both point to position 2.
the cycle starts at position 2, and 2 is the answer.

Finding the start of a cycle with no extra memory is exactly what 4.9.7 taught. We use the same two phases, with nums[i] in place of node.next.

The solution ​

python
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = 0                      # (1)
        while True:                          # (2)
            slow = nums[slow]                # (3)
            fast = nums[nums[fast]]          # (4)
            if slow == fast:                 # (5)
                break

        slow2 = 0                            # (6)
        while slow != slow2:                 # (7)
            slow = nums[slow]
            slow2 = nums[slow2]

        return slow                          # (8)
ts
function findDuplicate(nums: number[]): number {
  let slow = 0, fast = 0;                    // (1)
  do {                                       // (2)
    slow = nums[slow];                       // (3)
    fast = nums[nums[fast]];                 // (4)
  } while (slow !== fast);                   // (5)

  let slow2 = 0;                             // (6)
  while (slow !== slow2) {                   // (7)
    slow = nums[slow];
    slow2 = nums[slow2];
  }

  return slow;                               // (8)
}

Line by line ​

(1) Both pointers start at position 0, which is outside the cycle.

(2) Phase one: find a meeting point inside the cycle. We loop until the two pointers meet. There is always a cycle, so the walk never runs off the end. That is why there is no fast and fast.next check like the linked-list version had. In TypeScript, a do ... while loop runs its body once before checking, which matches Python's while True with a break.

(3) slow takes one step: follow the signpost at its position.

(4) fast takes two steps: follow the signpost, then follow the signpost there.

(5) Stop when they meet. They are now on the same position somewhere inside the cycle, not necessarily at its start.

(6) Phase two: start a second slow pointer at position 0.

(7) Move both one step at a time until they meet. From the algebra in 4.9.7, the distance from the start to the cycle's entrance equals the distance from the meeting point to the entrance, plus some whole number of laps. So after the same number of steps, both pointers arrive at the entrance together.

(8) The entrance position is the repeated value.

Trace ​

Take nums = [1, 3, 4, 2, 2].

Phase one.

Stepslow (one step)fast (two steps)Equal?
start00—
1nums[0] = 1nums[nums[0]] = nums[1] = 3no
2nums[1] = 3nums[nums[3]] = nums[2] = 4no
3nums[3] = 2nums[nums[4]] = nums[2] = 4no
4nums[2] = 4nums[nums[4]] = nums[2] = 4yes

They meet at position 4.

Phase two.

Stepslowslow2Equal?
start40no
1nums[4] = 2nums[0] = 1no
2nums[2] = 4nums[1] = 3no
3nums[4] = 2nums[3] = 2yes

They meet at 2. The answer is 2. ✓

Complexity, derived ​

Time. In phase one, slow reaches the cycle in at most n steps, and fast catches it within at most another n steps, for the same reason as in 4.9.7. In phase two, both pointers reach the entrance in at most n steps. That is at most about 3n steps, which is O(n).

Space. Three pointer numbers. The list is never changed. So the extra memory is O(1).

This is the only common solution that meets all three requirements: linear time, constant memory, and no changes to the list.

The binary search alternative ​

There is a second solution, and it is much easier to come up with under pressure.

Instead of searching the list, search the range of possible answers, 1 to n. Pick a middle value m, and count how many numbers in the list are at most m.

If there were no repeat at or below m, exactly m numbers would be at most m: one each of 1, 2, … , m. So:

  • If the count is more than m, some value at or below m must be repeated. Search the lower half.
  • Otherwise, the repeat is above m. Search the upper half.
python
def findDuplicate(self, nums):
    low, high = 1, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        count = sum(1 for x in nums if x <= mid)   # how many values are ≤ mid
        if count > mid:
            high = mid                             # the repeat is in [low, mid]
        else:
            low = mid + 1                          # the repeat is in [mid+1, high]
    return low

Each round counts the whole list, O(n), and halves the range, so there are about \log n rounds. That is O(n \log n) time and O(1) memory, and it does not change the list either. It is slower than the cycle method but meets the rules. This is binary search on the answer, which gets its own chapter in 4.11.

If the cycle idea does not come to you in an interview, offer this one. A correct O(n \log n) answer beats a stalled O(n) one.

Edge cases ​

  • The repeat appears many times, like [3, 3, 3, 3, 3]. Many signposts point to position 3. The cycle method still finds 3.
  • The smallest list, [1, 1]. Position 0 points to 1, and position 1 points to itself. The answer is 1.
  • The repeat is the largest value, like [1, 4, 4, 2, 4]. Works the same way.

Variations you will meet ​

  • If you were allowed to change the list, it becomes easy. You could make nums[abs(x)] negative as a "seen" mark, or swap each value to its home position. Both are O(n) time and O(1) memory.
  • Missing Number. One value from 0 to n is missing instead of repeated. That has a neat bit trick, in 4.30.5.

The general lesson: when every value is a valid position, you can follow values like pointers, and linked-list techniques start to work on a plain list.

What the interviewer will push on ​

"Why must there be a cycle?" n + 1 positions and only n values. Two positions share a value, so two signposts point to the same place.

"Why is position 0 outside the cycle?" No value is 0, so nothing points to position 0.

"Why is the cycle's entrance the repeated value?" It is the position that two different positions point to, and those two positions hold the same value.

"Is there another way?" Binary search on the answer. Naming both, and the trade-off between them, is the complete answer.

One thing to volunteer: explain why the obvious answers are banned before you solve it. "No extra memory rules out a set. No changes rule out sorting and marking. So the rules are pointing somewhere else." That reasoning is the real skill being tested.

Next: 4.9.9 LRU Cache. A design problem, and the clearest example in the book of two data structures covering each other's weakness.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet