Domain 2MediumCORE

Find the Duplicate Number

We are given an array nums of length $n + 1$ where every element is between $1$ and $n$. We know there is exactly one integer that appears two or more times, but we don't need to find all duplicates—just the value.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Two Pointers#Binary Search

287. Find the Duplicate Number

Model: qwen3.5:9b
Topics: Array,Two Pointers,Binary Search
FAANG asked: 1
Acceptance rate: 57.9%


Problem Breakdown

We are given an array nums of length n+1n + 1 where every element is between 11 and nn. We know there is exactly one integer that appears two or more times, but we don’t need to find all duplicates—just the value.

Key constraints from the follow-up questions dictate our solution path:

  1. No modification: We cannot sort in-place or mark visited indices by changing values (e.g., negating).
  2. Constant Space (O(1)O(1)): Using a Hash Set is O(n)O(n) space, which violates this constraint.
  3. Time Complexity < O(n2)O(n^2): Nested loops are out.

Implicitly, since we have n+1n+1 items but only nn unique possible values (Pigeonhole Principle), at least one collision must exist in the mapping of indices to values if we treat them as pointers. This structure allows us to model this problem using cycle detection logic similar to a Linked List Cycle II.

Intuition

A brute-force approach would be sorting (O(nlog⁡n)O(n \log n)) or checking every pair for duplicates (O(n2)O(n^2)). Both fail the space and time constraints respectively (sorting modifies array, O(n2)O(n^2) is too slow). A Hash Set solves it in linear time but uses extra memory.

The key insight comes from visualizing the input as a functional graph:

  • Each index i points to another node at value nums[i].
  • Since values are within [1, n], and array length is n+1n+1, every pointer lands on a valid index (except potentially 0 if we consider it outside range, but since indices go up to nn and values stop at nn, bounds are safe).
  • Because there is only one duplicate value appearing multiple times, two different nodes will point to the same next node. This creates exactly one cycle in this linked list structure.

We can use Floyd’s Tortoise and Hare algorithm (Cycle Detection) to find where that cycle begins. The entry point of the cycle corresponds to the duplicate number because it is the only value reachable from multiple distinct indices.

Approach

  1. Phase 1: Detect Cycle. Initialize two pointers, slow and fast. Move slow one step (nums[slow]) and fast two steps (nums[nums[fast]]). Since a cycle exists (guaranteed by constraints), they will eventually meet inside the loop.
  2. Phase 2: Find Cycle Start. Once pointers meet, reset slow to index 0 while keeping fast at the meeting point. Move both one step at a time (nums[ptr]). The first node where they coincide is the start of the cycle (the duplicate number).
  3. Why this works: In linked list theory, if there are aa nodes before the cycle and bb nodes in the cycle length, meeting point logic ensures that resetting one pointer to head allows them to meet at distance start from head.

Complexity Analysis

  • Time Complexity: O(n)O(n). Both pointers traverse a linear path proportional to array size. The first phase meets within ≤2n\le 2n steps; the second phase traverses another bounded number of nodes. Total is strictly linear.
  • Space Complexity: O(1)O(1). We only use two integer variables for pointers, regardless of input size.

Solution

class Solution:
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        # Phase 1: Detect cycle using Floyd's Tortoise and Hare
        slow = fast = nums[0]
        
        while True:
            slow = nums[slow]       # Move one step
            fast = nums[nums[fast]]  # Move two steps
            
            if slow == fast:
                break
        
        # Phase 2: Find the entrance to the cycle (the duplicate number)
        slow = 0 
        while True:
            slow = nums[slow]       # Advance one step from head
            fast = nums[fast]       # Advance one step from meeting point
            
            if slow == fast:
                return slow

Edge Cases Handled

  • Minimum Size (n=2n=2): The logic holds. If nums=[1, 1], pointers meet immediately or after minimal steps; the reset phase correctly identifies index/value overlap at value 1.
  • Duplicate appears multiple times: Even if a number repeats more than twice (e.g., [3, 3, 2, 4, 5, 6, 7]), it still forms exactly one cycle entry point because the graph structure is defined by index -> value. The duplicate value acts as the merge node.
  • Duplicate at start/end: Since we treat values as indices for traversal (values ∈[1,n]\in [1, n] and array length n+1n+1), boundary conditions are handled naturally without index out-of-bounds errors during pointer movement.