MediumArrayTwo PointersBinary SearchBit ManipulationPigeonhole PrincipleFloyd's Cycle Finding AlgorithmUpdated Sep 2026

287. Find the Duplicate Number

Asked at Walmart

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given an array nums of length n + 1. Every value in it is an integer between 1 and n. Exactly one value appears more than once (it may appear two or more times); every other value appears once.

Return that repeated value.

Two rules make this harder than it looks: you must not modify the array, and you may use only constant extra space (no hash set, no copy of the array).

Values point to indices

nums1342201234index 3 and index 4 both hold 2, so both point toindex 2jumps0132cycle0 → 1 → 3 → 2 → 4 → 2 ... the walk enters a cycle at 2
Read each value as a jump to that index. Because one value repeats, two indices jump to the same place, which closes a loop.

Constraints

  • ●1 <= n <= 10^5
  • ●nums.length == n + 1
  • ●1 <= nums[i] <= n
  • ●Every value appears once except exactly one value, which appears two or more times

Examples

Example 1
Inputnums = [1,3,4,2,2]
Output2
WhyThe values 1, 3 and 4 each appear once. The value 2 appears twice, so it is the repeated number.
Example 2
Inputnums = [3,1,3,4,2]
Output3
WhyHere 1, 4 and 2 appear once, while 3 appears twice. So the answer is 3.
Example 3
Inputnums = [3,3,3,3,3]
Output3
WhyEvery slot holds a 3. The repeated value is 3, and it appears far more than twice — that is allowed.

Asked At

1 companies
CompanyDifficulty
WalmartMediumView all Walmart questions →

How to Think About It

1

Brute force: For each element, scan all other elements to find a match — O(n²) time.

2

Sorting approach: Sort and check adjacent elements — O(n log n) time but violates the no-modify constraint.

3

Binary search on value range: Count elements ≤ mid to determine which half contains the duplicate.

4

Bit manipulation: Count set bits at each position across all numbers and compare with expected counts from 1..n.

5

Optimal: Floyd's tortoise and hare cycle detection — treat array values as pointers to find the cycle entrance.

Optimal Approach

Treat the array as a linked list where the value at index i is the next node index. Since a duplicate exists, two indices point to the same node, creating a cycle. Phase 1: Move slow one step and fast two steps until they meet inside the cycle. Phase 2: Reset slow to index 0 and move both one step at a time — their meeting point at the cycle entrance is the duplicate. This runs in O(n) time and O(1) space.

Floyd's tortoise and hare

nums1342201234slowfastPhase 1 start — slow at 0, fast at 0nums1342201234meetPhase 1 end — slow moves 1 step, fast moves 2 steps,they meet at index 2nums1342201234slowfastPhase 2 — reset slow to 0, then move both one step ata timeslow = nums[slow]fast = nums[nums[fast]]meeting index = duplicate value
Phase 1 finds a meeting point inside the loop. Phase 2 walks from index 0 and from the meeting point at the same speed; they collide at the loop entrance, which is the duplicate.
ComplexityTime O(n)Space O(1)The tortoise and hare each walk the array a constant number of times, and we only keep two index variables.

What Trips People Up in Real Interviews

1

Ask whether you can modify the array — the follow-up is always the constant-space version.

2

Explain the Pigeonhole Principle: n+1 values in range [1,n] guarantees a duplicate.

3

Map the array to a linked list: index i points to nums[i], creating a cycle with the duplicate as entrance.

4

Implement two-phase cycle detection: slow/fast meeting point, then restart slow from index 0.

5

Walk through [1,3,4,2,2] to show the cycle: 0→1→3→2→4→2→4...

Solution Code

O(n) time
class Solution:
    def findDuplicate(self, nums):
        slow = nums[0]
        fast = nums[nums[0]]
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]
        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Find the Duplicate Number problem?

Given an array of n+1 integers where each integer is between 1 and n inclusive, find the one duplicate number without modifying the array and using only constant extra space. The duplicate may appear more than once but there is guaranteed to be exactly one repeated value.

How do you solve Find the Duplicate Number?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Find the Duplicate Number?

Find the Duplicate Number is asked at Walmart. It is a medium difficulty problem.

What are common mistakes on Find the Duplicate Number?
  • Ask whether you can modify the array — the follow-up is always the constant-space version.
  • Explain the Pigeonhole Principle: n+1 values in range [1,n] guarantees a duplicate.
  • Map the array to a linked list: index i points to nums[i], creating a cycle with the duplicate as entrance.
  • Implement two-phase cycle detection: slow/fast meeting point, then restart slow from index 0.
  • Walk through [1,3,4,2,2] to show the cycle: 0→1→3→2→4→2→4...