Solution Approach

We use the standard binary search template to find the duplicate. The key insight is defining the feasible function:

Feasible Function: feasible(x) = count of numbers ≤ x > x

This returns true when there's excess (meaning the duplicate is ≤ x), creating a false, false, ..., true, true pattern.

Template Implementation:

left, right = 1, n
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    count = sum(1 for num in nums if num <= mid)
    if count > mid:  # feasible condition
        first_true_index = mid
        right = mid - 1  # search for smaller duplicate
    else:
        left = mid + 1

return first_true_index

How it works:

1. Initialize left = 1, right = n (value range, not indices), and first_true_index = -1
2. Use while left <= right loop
3. Count how many numbers are ≤ mid
4. If count > mid, we found excess, so first_true_index = mid and search left with right = mid - 1
5. If count ≤ mid, no excess yet, search right with left = mid + 1
6. Return first_true_index as the duplicate number

Time and Space Complexity:

• Time: O(n log n) - Binary search takes O(log n) iterations, each counting in O(n)
• Space: O(1) - Only using a few variables

Example Walkthrough

Let's walk through the solution with array [1, 3, 4, 2, 2] using the binary search template.

Initial Setup:

• left = 1, right = 4 (value range)
• first_true_index = -1
• Feasible condition: count(≤ mid) > mid

Iteration 1:

• left = 1, right = 4
• mid = (1 + 4) // 2 = 2
• Count elements ≤ 2: 1, 2, 2 → count = 3
• Is 3 > 2? Yes! (feasible)
• Update: first_true_index = 2, right = mid - 1 = 1

Iteration 2:

• left = 1, right = 1
• mid = (1 + 1) // 2 = 1
• Count elements ≤ 1: 1 → count = 1
• Is 1 > 1? No! (not feasible)
• Update: left = mid + 1 = 2

Termination:

• left = 2 > right = 1, exit loop
• Return first_true_index = 2

Verification:

• At mid = 2: count = 3 > 2, meaning there's excess in [1, 2], so the duplicate is 2 or less
• At mid = 1: count = 1 = 1, no excess, so the duplicate is greater than 1
• Therefore, the duplicate is exactly 2 ✓

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. Using Wrong Binary Search Template Variant

Pitfall: Using while left < right with right = mid instead of the standard template with while left <= right and right = mid - 1.

# WRONG - different template variant
while left < right:
    mid = (left + right) // 2
    if count > mid:
        right = mid
    else:
        left = mid + 1
return left

Solution: Use the standard binary search template with first_true_index:

# CORRECT - standard template
left, right = 1, n
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    count = sum(1 for num in nums if num <= mid)
    if count > mid:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index

2. Wrong Search Range (Indices vs Values)

Pitfall: Using array indices [0, n] instead of value range [1, n].

# WRONG - searching indices
left, right = 0, len(nums) - 1

Solution: Search on the value range since we're looking for which value is duplicated:

# CORRECT - searching values
n = len(nums) - 1  # max value is n
left, right = 1, n

3. Incorrect Count Comparison

Pitfall: Using count >= mid instead of count > mid.

# WRONG - this would incorrectly flag non-duplicates
if count >= mid:  # Should be >

Why it matters:

• For a non-duplicate value x, count(≤ x) = x exactly
• Only when there's a duplicate does count(≤ x) > x
• Using >= incorrectly flags all values as potential duplicates

4. Confusing with Floyd's Cycle Detection

Pitfall: This problem has two classic solutions - binary search and Floyd's cycle detection. Don't mix them.

Solution: The binary search approach (shown here) is more intuitive and directly uses the template. Floyd's cycle detection is a different approach that treats the array as a linked list.