Problem Description

You are given an array nums containing n + 1 integers, where each integer is in the range [1, n] inclusive.

The array has exactly one repeated number that appears more than once. Your task is to find and return this duplicate number.

Constraints:

• You cannot modify the input array nums
• You must use only constant extra space (O(1) space complexity)

Example understanding: If n = 4, the array has 5 elements, and each element is between 1 and 4. Since there are 5 elements but only 4 possible distinct values, by the Pigeonhole Principle, at least one number must appear twice.

The solution uses binary search on the value range [1, n] rather than on array indices. For each mid-value x, it counts how many elements in the array are less than or equal to x. If this count is greater than x, it means there must be a duplicate in the range [1, x]. Otherwise, the duplicate is in the range [x+1, n].

The key insight is that without a duplicate, there should be exactly x numbers that are ≤ x. If we count more than x numbers that are ≤ x, then at least one number in the range [1, x] appears multiple times.

Intuition

The key observation starts with understanding what happens in a normal scenario without duplicates. If we have numbers from 1 to n with no duplicates, then for any number x in this range, there should be exactly x numbers that are less than or equal to x. For example, if x = 3, there should be exactly 3 numbers: 1, 2, 3.

But what happens when there's a duplicate? If a number in the range [1, x] appears twice, then when we count how many numbers are ≤ x, we'll get more than x. This is because the duplicate creates an "excess" count.

Think of it like this: imagine you're looking for a duplicate in [1, 2, 3, 3, 4]. If you ask "how many numbers are ≤ 3?", you get 4 numbers (1, 2, 3, 3), but in a normal case without duplicates, there should only be 3. This excess tells us the duplicate must be in the range [1, 3].

This observation naturally leads to a binary search approach on the value range rather than array indices. We can repeatedly divide the range [1, n] in half and check which half contains the duplicate by counting elements. If count(≤ mid) > mid, the duplicate is in [1, mid]; otherwise, it's in [mid+1, n].

The beauty of this approach is that we're using the mathematical property of the problem itself - the constraint that numbers are in range [1, n] - rather than needing to track array positions or modify the array. We're essentially using the Pigeonhole Principle in a binary search fashion to narrow down where the duplicate must be.

Solution Approach

The solution implements binary search on the value range [1, n] to find the duplicate number. Here's how the implementation works:

Binary Search Setup: We use bisect_left from Python's bisect module to perform the binary search. The search range is range(len(nums)), which represents values from 0 to n (since the array has n+1 elements).

Key Function: The helper function f(x) is the core logic:

def f(x: int) -> bool:
    return sum(v <= x for v in nums) > x

This function returns True if the count of elements ≤ x is greater than x, indicating that the duplicate is in the range [1, x].

How Binary Search Works Here:

1. bisect_left searches for the leftmost position where f(x) returns True
2. It starts with the middle value of the range
3. If f(mid) is True, it means the duplicate is in [1, mid], so we search the left half
4. If f(mid) is False, the duplicate is in [mid+1, n], so we search the right half
5. The search continues until we converge on the exact duplicate value

Example Walkthrough: For array [1, 3, 4, 2, 2]:

• Check x = 2: count of elements ≤ 2 is 3 (which are 1, 2, 2). Since 3 > 2, f(2) = True
• Check x = 1: count of elements ≤ 1 is 1. Since 1 = 1, f(1) = False
• Binary search narrows down to x = 2 as the duplicate

Time and Space Complexity:

• Time: O(n log n) - Binary search takes O(log n) iterations, and each iteration counts elements in O(n)
• Space: O(1) - Only using a few variables, meeting the constant space requirement

Example Walkthrough

Let's walk through the solution with array [1, 3, 4, 2, 2], where n = 4 (array has 5 elements).

Initial Setup:

• Search range: [1, 4] (possible values)
• We need to find which value appears twice

Binary Search Process:

Iteration 1:

• mid = (1 + 4) / 2 = 2
• Count elements ≤ 2: We find 1 and 2, 2 → count = 3
• Is 3 > 2? Yes! So duplicate is in range [1, 2]
• Update: right = 2

Iteration 2:

• New range: [1, 2]
• mid = (1 + 2) / 2 = 1
• Count elements ≤ 1: We find only 1 → count = 1
• Is 1 > 1? No! So duplicate is in range [2, 2]
• Update: left = 2

Convergence:

• left = right = 2
• The duplicate number is 2

Verification: Let's verify our logic at each step:

• When checking mid = 2: We counted 3 elements (1, 2, 2) that are ≤ 2. Without duplicates, there should only be 2 elements (1, 2). The excess tells us the duplicate is somewhere in [1, 2].
• When checking mid = 1: We counted 1 element (1) that is ≤ 1. This is exactly what we'd expect without duplicates, so the duplicate must be greater than 1.

The algorithm efficiently narrows down the search space by half each time, converging on the duplicate value 2 without modifying the array or using extra space beyond a few variables.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array nums. This is because:

• The bisect_left function performs binary search on the range [0, len(nums)), which requires O(log n) iterations
• For each iteration of the binary search, the key function f(x) is called, which computes sum(v <= x for v in nums), taking O(n) time to iterate through all elements in nums
• Therefore, the total time complexity is O(n) × O(log n) = O(n × log n)

The space complexity is O(1). This is because:

• The binary search only uses a constant amount of extra space for variables
• The function f(x) uses a generator expression sum(v <= x for v in nums) which doesn't create additional data structures, only iterating through the existing array
• No additional arrays or data structures proportional to the input size are created

Common Pitfalls

1. Off-by-One Error in Binary Search Range

The most common pitfall is incorrectly setting up the binary search range. Since the valid numbers are [1, n] but bisect_left with range(len(nums)) gives us [0, n], the code might return incorrect results.

The Issue:

• range(len(nums)) produces [0, 1, 2, ..., n]
• But our valid numbers are [1, 2, ..., n]
• If the duplicate is 1, the function f(0) would be checked, which doesn't make logical sense

Solution: Use range(1, len(nums)) to search only valid values:

duplicate = bisect_left(range(1, len(nums)), True, key=count_less_than_or_equal)

2. Incorrect Count Comparison Logic

Another pitfall is using the wrong comparison in the counting function. Some might mistakenly use >= instead of >.

The Issue:

# Incorrect - this would fail for non-duplicate numbers
def count_less_than_or_equal(target: int) -> bool:
    count = sum(1 for num in nums if num <= target)
    return count >= target  # Wrong! Should be >

Why it matters:

• For a non-duplicate number x, there are exactly x numbers ≤ x
• Only when there's a duplicate in range [1, x] will the count exceed x
• Using >= would incorrectly flag all numbers as potential duplicates

3. Using Floyd's Cycle Detection Without Understanding Constraints

Many developers default to Floyd's cycle detection algorithm (tortoise and hare) because it's a classic solution for this problem. However, the given code uses binary search instead.

The Issue: Mixing approaches or trying to "optimize" by switching algorithms mid-implementation:

# Don't mix approaches - stick to one algorithm
def findDuplicate(self, nums: List[int]) -> int:
    # Started with binary search setup
    def count_less_than_or_equal(target: int) -> bool:
        # ... binary search logic
  
    # Then suddenly switching to cycle detection
    slow = fast = nums[0]  # This creates confusion!

Solution: Commit to one approach. Binary search is more intuitive here and doesn't require treating the array as a linked list.

4. Inefficient Counting Implementation

Using sum() with a generator expression is elegant but can be misunderstood or implemented inefficiently.

Less Readable Alternative:

def count_less_than_or_equal(target: int) -> bool:
    count = len([num for num in nums if num <= target])  # Creates unnecessary list
    return count > target

Better Implementation:

def count_less_than_or_equal(target: int) -> bool:
    count = 0
    for num in nums:
        if num <= target:
            count += 1
            if count > target:  # Early termination optimization
                return True
    return False

This version can return early once we know the count exceeds the target, potentially saving iterations.