Find the Duplicate Number — Binary Search on Count [LC 287, Google, Amazon]

Problem Statement#

Given an array nums containing n + 1 integers where each integer is in [1, n], there is exactly one repeated number. Find and return it. You must not modify the array and use only O(1) extra space.

Constraints:

• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• All integers appear once except for exactly one which appears two or more times

Input:  nums = [1,3,4,2,2]
Output: 2

Input:  nums = [3,1,3,4,2]
Output: 3

Why This Problem Matters#

LC 287 is asked by Google and Amazon because it has multiple valid approaches at different time/space complexity levels, and the interviewer can probe depth by asking for progressively more constrained solutions. The binary search approach (O(n log n) time, O(1) space) uses a clever counting argument based on the pigeonhole principle, while the optimal Floyd's cycle detection (O(n) time, O(1) space) treats the array as a linked list.

The binary search insight — "if count of elements <= mid is greater than mid, a duplicate must exist in [1, mid]" — is based on the pigeonhole principle and is the same reasoning used in many existence-proof problems.

The Core Insight#

Binary search on value (pigeonhole principle): For any value mid in [1, n], count how many elements in nums are <= mid. In a duplicate-free array with values in [1, n], exactly mid elements would be <= mid. If count > mid, by the pigeonhole principle, there must be a duplicate in [1, mid]. Otherwise, the duplicate is in [mid+1, n].

This is a left-boundary search: find the smallest mid where count(nums, mid) > mid.

Visual Dry Run#

Input: nums = [1, 3, 4, 2, 2], n = 4

Search range: lo = 1, hi = 4

Solution (Optimal)#

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        lo, hi = 1, len(nums) - 1  # search value range [1, n]
 
        while lo < hi:
            mid = lo + (hi - lo) // 2
            # Count elements <= mid
            count = sum(1 for x in nums if x <= mid)
 
            if count > mid:
                # Duplicate is in [lo, mid] — pigeonhole principle
                hi = mid
            else:
                # Duplicate is in [mid+1, hi]
                lo = mid + 1
 
        return lo

var findDuplicate = function(nums) {
    let lo = 1, hi = nums.length - 1;
 
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        let count = 0;
        for (const x of nums) {
            if (x <= mid) count++;
        }
 
        if (count > mid) {
            hi = mid;  // duplicate in [lo, mid]
        } else {
            lo = mid + 1;  // duplicate in [mid+1, hi]
        }
    }
 
    return lo;
};

Time: O(n log n) — O(log n) binary search iterations, each O(n) count pass Space: O(1) — only pointer and counter variables

Floyd's Cycle Detection (O(n) time, O(1) space): Treat the array as a linked list where nums[i] points to the next node. The duplicate creates a cycle. Use slow/fast pointers to find the cycle entry point.

def findDuplicate(nums):
    slow, fast = nums[0], nums[nums[0]]
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
    fast = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

Common Mistakes#

• Sorting the array first — the problem says you must not modify the array (though this is sometimes relaxed).
• Using a hash set — works in O(n) time and space but violates the O(1) space constraint.
• Confusing the search range: binary search is on values [1, n], not on array indices [0, n].
• Off-by-one: hi = len(nums) - 1 gives the value range [1, n] correctly since nums.length = n + 1.

Interview Tips#

• Mention all three approaches upfront: hash set (O(n)/O(n)), binary search (O(n log n)/O(1)), Floyd's cycle (O(n)/O(1)).
• The binary search approach is the expected answer when the interviewer emphasises O(1) space but O(n log n) time is acceptable.
• Explain the pigeonhole principle clearly: "In a clean array of n distinct values in [1,n], exactly mid values fall in [1,mid]. More than mid means a duplicate must be there."
• Floyd's cycle detection is the optimal O(n)/O(1) solution and demonstrates advanced algorithmic knowledge.

Follow-up Questions#

• Why can't you use sorting? The problem states you must not modify the array. Sorting is an in-place O(n log n) mutation.
• Can you find the duplicate in O(n) without modifying the array? Yes — Floyd's cycle detection treats the array as an implicit linked list.
• What if there are multiple duplicates? The pigeonhole binary search still finds one duplicate, but it may not find all. You'd need a different approach for the multi-duplicate case.
• LC 268 (Missing Number): Related problem — find the one missing number in [0, n]. Use XOR or sum formula.

Key Takeaways#

• LC 287 binary search approach uses the pigeonhole principle: count elements <= mid; if count > mid, the duplicate is in [1, mid] (left-boundary search on values).
• The search range is the value range [1, n], not the index range — this is binary search on the answer space, not on the array.
• Time is O(n log n): O(log n) binary search iterations, each requiring an O(n) linear scan to count.
• Space is O(1) — no auxiliary data structures beyond a few integer variables.
• Floyd's cycle detection solves this in O(n) time, O(1) space — the optimal solution, treating the array as an implicit linked list where indices are nodes and values are edges.
• Google and Amazon ask this problem specifically to explore the space of valid approaches and test whether candidates can reason about constraints (no modification, O(1) space).
• The pigeonhole reasoning generalises to any problem where "if count exceeds expected, something wrong must be in this range."