← all entries
A-042● Day 422026.06.17mediumleetcode #287neetcode150

Find the Duplicate Number

#array#two-pointers#binary-search#bit-manipulation
↗ leetcode #287 · find-the-duplicate-number
01

Problem

· problem
P.042

Find the Duplicate Number

↗ leetcode #287

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. You must solve the problem without modifying the array nums and using only constant extra space.

constraints
  • · 1 ≤ n ≤ 10^5
  • · nums.length == n + 1
  • · 1 ≤ nums[i] ≤ n
  • · Precisely one integer appears two or more times
// paraphrased summary — see source for full text
examples
example 1input → output
[1,3,4,2,2]
2
example 2input → output
[3,1,3,4,2]
3
example 3input → output
[3,3,3,3,3]
3
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Can the duplicate number appear more than twice, or only twice?
  • ☐
    Why is it important not to modify the input array?
  • ☐
    What does 'constant extra space' mean in this context?
  • ☐
    Is it guaranteed that at least one duplicate must exist?
  • ☐
    Can we solve this using a hash set in O(n) time?
  • ☐
    Can we sort the array and check for adjacent duplicates?
  • ☐
    Can we treat array indices as pointers in a linked list?
  • ☐
    Does the meeting point of slow and fast pointers directly give us the duplicate?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize two pointers
○
slow, fast = 0, 0
○
slow, fast = 0, 1
○
slow, fast = 1, 1
step 2· Phase 1: Detect cycle with speed difference│ nested
○
fast = nums[nums[fast]]
○
slow = nums[slow]; fast = nums[fast]
○
slow = nums[slow]; fast = nums[nums[nums[fast]]]
step 3· Check if cycle is detected│ │ nested
○
if slow == fast:
○
if slow < fast:
○
if slow != fast:
step 4· Phase 2: Reset pointer for entrance detection
○
slow2 = 0
○
slow = 0; slow2 = slow
○
slow2 = fast
step 5· Phase 2: Find and return duplicate│ nested
○
return slow
○
return slow2
○
return fast
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def findDuplicate(self, nums: List[int]) -> int:
3
        slow, fast = 0, 0
4
        while True:
5
            slow = nums[slow]
6
            fast = nums[nums[fast]]
7
            if slow == fast:
8
                break
9
10
        slow2 = 0
11
        while True:
12
            slow = nums[slow]
13
            slow2 = nums[slow2]
14
            if slow == slow2:
15
                return slow
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[1,3,4,2,2]
→
2
case 2
[3,1,3,4,2]
→
3
case 3
[3,3,3,3,3]
→
3
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.