Data Structures & AlgorithmsSearch in Rotated Arrays

Search in Rotated Arrays

LevelIntermediate

Duration60 mins

TopicSearch in Rotated Arrays

3 / 4

Handling Duplicates in Rotated Arrays

When Duplicates Break Everything

The elegant binary search algorithm we developed for rotated arrays with distinct elements has a hidden assumption: every value uniquely identifies its position relative to the rotation point. When we check nums[low] <= nums[mid], we can definitively conclude whether the left half is sorted.

Duplicates shatter this assumption.

Consider the array [1, 1, 1, 1, 1, 2, 1, 1, 1]. When nums[low] = 1, nums[mid] = 1, and nums[high] = 1, we have no information about which half is sorted. The rotation point could be anywhere. This single insight has profound implications for the algorithm's complexity guarantees.

The Worst-Case Reality

With duplicates, the worst-case time complexity degrades from O(log n) to O(n). This isn't a failure of algorithm design—it's a fundamental limitation. When nums[low] = nums[mid] = nums[high], we cannot eliminate half the array with one comparison. Understanding why this happens and how to handle it is essential for interviews.

What You Will Learn

By the end of this page, you will understand why duplicates break the O(log n) guarantee, how to modify the algorithm to handle duplicates correctly, and how to explain the complexity trade-offs to an interviewer.

Why Duplicates Break the Algorithm

Let's understand precisely why duplicates cause problems. The key check in our algorithm is:

if nums[low] <= nums[mid]:  # Left half is sorted

With distinct elements, this check is reliable:

If nums[low] <= nums[mid], the elements from low to mid are in ascending order
If nums[low] > nums[mid], the rotation point is in the left half

With duplicates, the check becomes ambiguous:

Consider [2, 2, 2, 3, 1, 2, 2]. Here:

nums[0] = 2, nums[3] = 3, nums[6] = 2
Rotation point is between index 3 and 4 (between 3 and 1)
Check: nums[0] <= nums[3]? Is 2 <= 3? Yes.
Conclusion: Left half [2, 2, 2, 3] is sorted. ✓ Correct!

But now consider [1, 1, 1, 1, 1, 2, 1, 1, 1]:

nums[0] = 1, nums[4] = 1, nums[8] = 1
Rotation point is between index 5 and 6 (between 2 and 1)
Check: nums[0] <= nums[4]? Is 1 <= 1? Yes.
Conclusion: Left half is sorted?

WRONG! The left half [1, 1, 1, 1, 1] appears sorted, but the rotation point (value 2, then back to 1) is in the right half. Our check passes, but we can't distinguish this from the case where the entire array is [1, 1, 1, 1, 1, 1, 1, 1, 1] with no rotation.

The Pathological CaseWhen all boundary values are identical, we have zero information.

Input

nums = [1, 1, 1, 1, 1, 2, 1, 1, 1], target = 2

Output

low = 0, mid = 4, high = 8
nums[0] = 1, nums[4] = 1, nums[8] = 1

Check: nums[low] <= nums[mid]?
       1 <= 1? YES

Conclusion: Left half should be sorted.

But wait! The actual values are:
Left half:  [1, 1, 1, 1, 1] - Sorted ✓
Right half: [1, 2, 1, 1, 1] - Contains the rotation!

If we assume left half is sorted and target=2 is not in [1,1],
we'd search right half → Happens to be correct by luck.

Now try: nums = [2, 1, 1, 1, 1, 1, 1, 1, 1], target = 1
mid = 4, nums[0]=2, nums[4]=1
Check: nums[0] <= nums[4]? 2 <= 1? NO
So right half should be sorted...

Right half: [1, 1, 1, 1, 1] - Sorted ✓
Left half: [2, 1, 1, 1] - Contains rotation ✓

Correct again! But...

Explanation

The critical case is when nums[low] = nums[mid] = nums[high]. We genuinely cannot determine which half is sorted.

The Unbreakable Ambiguity

When nums[low] = nums[mid] = nums[high], there is NO comparison-based way to determine which half contains the rotation point. The only option is to reduce the problem size by a constant factor (typically eliminating just one element at a time), leading to O(n) worst case.

The Modified Algorithm for Duplicates

The solution is surprisingly simple: when we encounter the ambiguous case (nums[low] = nums[mid] OR nums[mid] = nums[high]), we can't safely eliminate half the array. Instead, we shrink the search space by just one element.

The strategy:

If nums[low] = nums[mid] = nums[high], we cannot determine which half is sorted
In this case, increment low and decrement high (skip the duplicate boundaries)
Continue with the standard algorithm

This handles ambiguity at the cost of occasionally making O(1) progress instead of halving.

Converting Mermaid diagram...

search_rotated_duplicates.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
def search_with_duplicates(nums: list[int], target: int) -> bool:
    """
    Search for target in a rotated sorted array that MAY contain duplicates.
    
    NOTE: Returns bool (existence), not index, because duplicates make
    index less meaningful and this matches LeetCode's problem formulation.
    
    Args:
        nums: A rotated sorted array possibly with duplicates
        target: The value to search for
        
    Returns:
        True if target exists in the array, False otherwise
        
    Time Complexity: O(log n) average, O(n) worst case
    Space Complexity: O(1)
    
    The worst case happens when most/all elements are the same except one.
    Example: [1,1,1,1,1,2,1,1,1] - we may need to check almost every element.
    """
    if not nums:
        return False
    
    low, high = 0, len(nums) - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        # Found the target
        if nums[mid] == target:
            return True
        
        # CRITICAL: Handle the ambiguous case
        # When nums[low] = nums[mid] = nums[high], we cannot determine
        # which half is sorted. We must shrink the search space manually.
        if nums[low] == nums[mid] == nums[high]:
            low += 1
            high -= 1
            continue  # Re-evaluate with smaller range
        
        # Now we can apply the standard logic
        # At least one of the inequalities must be strict
        
        if nums[low] <= nums[mid]:
            # Left half is sorted
            if nums[low] <= target < nums[mid]:
                high = mid - 1  # Target in sorted left half
            else:
                low = mid + 1  # Target in right half
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[high]:
                low = mid + 1  # Target in sorted right half
            else:
                high = mid - 1  # Target in left half
    
    return False
 
 
def search_with_duplicates_verbose(nums: list[int], target: int) -> bool:
    """Same algorithm with detailed tracing."""
    if not nums:
        return False
    
    low, high = 0, len(nums) - 1
    iteration = 0
    
    print(f"Searching for {target} in {nums}")
    print("=" * 70)
    
    while low <= high:
        mid = low + (high - low) // 2
        iteration += 1
        
        print(f"\nIteration {iteration}: low={low}, mid={mid}, high={high}")
        print(f"  Values: nums[{low}]={nums[low]}, nums[{mid}]={nums[mid]}, nums[{high}]={nums[high]}")
        
        if nums[mid] == target:
            print(f"  ✓ FOUND! Target {target} at index {mid}")
            return True
        
        if nums[low] == nums[mid] == nums[high]:
            print(f"  ⚠️ AMBIGUOUS: All boundary values = {nums[low]}")
            print(f"  Cannot determine sorted half, shrinking by 1 each side")
            low += 1
            high -= 1
            continue
        
        if nums[low] <= nums[mid]:
            print(f"  Left half sorted: [{nums[low]}...{nums[mid]}]")
            if nums[low] <= target < nums[mid]:
                print(f"  Target in sorted left half")
                high = mid - 1
            else:
                print(f"  Target NOT in sorted left half")
                low = mid + 1
        else:
            print(f"  Right half sorted: [{nums[mid]}...{nums[high]}]")
            if nums[mid] < target <= nums[high]:
                print(f"  Target in sorted right half")
                low = mid + 1
            else:
                print(f"  Target NOT in sorted right half")
                high = mid - 1
    
    print(f"\n✗ NOT FOUND after {iteration} iterations")
    return False
 
 
# Demonstrations
if __name__ == "__main__":
    print("\n" + "=" * 70)
    print("TEST 1: Duplicates but no ambiguity")
    print("=" * 70)
    search_with_duplicates_verbose([2, 5, 6, 0, 0, 1, 2], 0)
    
    print("\n" + "=" * 70)
    print("TEST 2: Pathological case - many duplicates")
    print("=" * 70)
    search_with_duplicates_verbose([1, 1, 1, 1, 1, 2, 1, 1, 1], 2)
    
    print("\n" + "=" * 70)
    print("TEST 3: All same values - target not present")
    print("=" * 70)
    search_with_duplicates_verbose([1, 1, 1, 1, 1], 2)
    
    print("\n" + "=" * 70)
    print("TEST 4: Worst case - degenerate to linear")
    print("=" * 70)
    arr = [1] * 100 + [2] + [1] * 100  # 201 elements, mostly 1s
    print(f"Array of 201 elements (mostly 1s), searching for 2")
    result = search_with_duplicates(arr, 2)
    print(f"Result: {result}")

Complexity Analysis with Duplicates

Understanding the complexity behavior is crucial for interview discussions. Let's analyze both average and worst cases.

Complexity Comparison: Distinct vs Duplicate Elements
Scenario	Distinct Elements	With Duplicates
Best Case	O(1) - target at mid	O(1) - target at mid
Average Case	O(log n)	O(log n) - if duplicates are limited
Worst Case	O(log n)	O(n) - when nums[low]=nums[mid]=nums[high]
Space	O(1)	O(1)

Why O(n) worst case?

In the worst case with duplicates, every iteration might only eliminate 2 elements (one from each end). Consider searching for 0 in:

[1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]

At each step:

nums[low] = 1, nums[mid] = 1, nums[high] = 1
We increment low and decrement high
We eliminate 2 elements per iteration

For an array of n elements, we need approximately n/2 iterations = O(n).

Can we do better?

Unfortunately, no—at least not with comparison-based algorithms. When all boundary values are identical, there is no information to distinguish which half contains the rotation point. This is a fundamental limitation, not an algorithm deficiency.

Interview Insight

If an interviewer asks whether you can achieve O(log n) with duplicates, the correct answer is: 'No, not in the worst case. When all visible boundary values are identical, we have no information to eliminate half the array. The best we can guarantee is O(log n) average case when duplicates are limited.'

Average case analysis:

If duplicates are sparse (most elements are distinct), the algorithm still performs close to O(log n) because:

The ambiguous case (nums[low] = nums[mid] = nums[high]) occurs rarely
Most iterations still halve the search space
Only occasional O(1) reductions don't significantly impact overall logarithmic behavior

In practice, if you expect limited duplicates, this algorithm remains efficient. Only in adversarial or highly degenerate inputs does it approach O(n).

Alternative Approaches and Trade-offs

Given the limitations with duplicates, are there alternative strategies? Let's examine several approaches and their trade-offs.

Alternative Strategies

•
Approach 1: Skip duplicates aggressively Instead of just low++, high--, skip all duplicates at the boundaries:
```
while low < high and nums[low] == nums[low+1]: low += 1
while low < high and nums[high] == nums[high-1]: high -= 1
```
This can help in some cases but doesn't change worst-case complexity. If ALL elements are the same except one, we still need O(n).
•
Approach 2: Find pivot first, then binary search First find the rotation point (minimum element), then do standard binary search on the appropriate sorted half.
- Pro: Separates concerns
- Con: Still O(n) worst case for finding pivot with duplicates
- Con: Two passes instead of one
•
Approach 3: Hash set for existence check If you only need existence (not index), preprocess into a hash set:
- Pro: O(1) lookup after O(n) preprocessing
- Con: O(n) extra space
- Con: Not useful for single queries
This is worth mentioning if the interviewer values practical thinking.
•
Approach 4: Accept linear search If duplicates are expected and array is small, a simple linear search is:
- Simpler to implement
- Same worst-case complexity
- Lower constant factors (no repeated comparisons)
For arrays under ~1000 elements with many duplicates, linear search might actually be faster!

alternative_approaches.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# Alternative 1: Aggressive duplicate skipping
def search_skip_duplicates(nums: list[int], target: int) -> bool:
    """Skip runs of duplicates at boundaries."""
    if not nums:
        return False
    
    low, high = 0, len(nums) - 1
    
    while low <= high:
        # Skip duplicates at low end
        while low < high and nums[low] == nums[low + 1]:
            low += 1
        
        # Skip duplicates at high end
        while low < high and nums[high] == nums[high - 1]:
            high -= 1
        
        mid = low + (high - low) // 2
        
        if nums[mid] == target:
            return True
        
        # Now apply standard logic (less likely to hit ambiguous case)
        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
    
    return False
 
 
# Alternative 2: Find pivot first, then search
def find_rotation_index_with_dups(nums: list[int]) -> int:
    """Find index of minimum element (rotation point)."""
    low, high = 0, len(nums) - 1
    
    while low < high:
        mid = low + (high - low) // 2
        
        if nums[mid] > nums[high]:
            low = mid + 1
        elif nums[mid] < nums[high]:
            high = mid
        else:
            # nums[mid] == nums[high], can't decide
            high -= 1
    
    return low
 
 
def search_two_pass(nums: list[int], target: int) -> bool:
    """Find pivot, then binary search appropriate half."""
    if not nums:
        return False
    
    pivot = find_rotation_index_with_dups(nums)
    n = len(nums)
    
    # Standard binary search, adjusted for rotation
    low, high = 0, n - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        real_mid = (mid + pivot) % n  # Adjust for rotation
        
        if nums[real_mid] == target:
            return True
        elif nums[real_mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return False
 
 
# Compare approaches
def compare_approaches():
    test_cases = [
        ([2, 5, 6, 0, 0, 1, 2], 0),
        ([1, 1, 1, 1, 1, 2, 1, 1, 1], 2),
        ([1, 1, 1, 1, 1], 2),
        ([3, 1, 1], 3),
    ]
    
    print("Comparing Approaches")
    print("=" * 60)
    
    for arr, target in test_cases:
        result1 = search_skip_duplicates(arr, target)
        result2 = search_two_pass(arr, target)
        
        print(f"Array: {arr}, Target: {target}")
        print(f"  Skip duplicates: {result1}")
        print(f"  Two-pass: {result2}")
        print()
 
 
compare_approaches()

Edge Cases Specific to Duplicates

Duplicates introduce several edge cases that don't exist with distinct elements. Understanding these is crucial for a robust implementation.

Duplicate-Specific Edge Cases

•All elements identical: [1, 1, 1, 1, 1] — Returns true if target=1, false otherwise. Algorithm degrades to O(n) but is correct.
•Two distinct values, many duplicates: [1, 1, 1, 2, 2, 2] — Rotation can be anywhere between blocks. Handle boundary carefully.
•Duplicates at rotation point: [2, 2, 1, 1] — The rotation point separates the two duplicate blocks. Our algorithm handles this.
•Target equals boundary duplicates: [1, 1, 1, 2, 1, 1, 1], target=1 — Must search both halves because target appears in both.
•Single non-duplicate: [1, 1, 1, 2, 1, 1, 1], target=2 — The unique element is the target. May need to search through duplicates to find it.
•Rotation at different points in duplicate runs: [1, 1, 2, 1, 1] vs [1, 2, 1, 1, 1] — Same elements, different rotations. Both handled correctly.

duplicate_edge_cases_test.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
def test_duplicate_edge_cases(search_fn):
    """Comprehensive test suite for duplicate handling."""
    
    test_cases = [
        # (array, target, expected, description)
        ([1, 1, 1, 1, 1], 1, True, "All same - target present"),
        ([1, 1, 1, 1, 1], 2, False, "All same - target absent"),
        ([2, 2, 2, 0, 1], 0, True, "Rotation amid duplicates"),
        ([2, 2, 2, 0, 2], 0, True, "Target in rotation gap"),
        ([1, 1, 1, 2, 1, 1, 1], 2, True, "Single non-duplicate target"),
        ([1, 1, 1, 2, 1, 1, 1], 1, True, "Target in duplicate regions"),
        ([1, 1, 1, 2, 1, 1, 1], 3, False, "Target not present"),
        ([3, 1, 1], 3, True, "Minimum duplicates, target at start"),
        ([1, 1, 3], 3, True, "Minimum duplicates, target at end"),
        ([1, 1, 1, 2, 2, 2, 1, 1, 1], 2, True, "Block of different value"),
        ([2, 2, 2, 1, 1, 1, 2, 2, 2], 1, True, "Block in middle"),
        ([2, 2, 1, 2, 2], 1, True, "Single different value in middle"),
        ([], 1, False, "Empty array"),
        ([1], 1, True, "Single element - present"),
        ([1], 0, False, "Single element - absent"),
    ]
    
    print("Testing Duplicate Edge Cases")
    print("=" * 70)
    
    passed = failed = 0
    
    for arr, target, expected, desc in test_cases:
        result = search_fn(arr, target)
        status = "✓" if result == expected else "✗"
        
        if result == expected:
            passed += 1
        else:
            failed += 1
            print(f"{status} FAIL: {desc}")
            print(f"    Array: {arr}, Target: {target}")
            print(f"    Expected: {expected}, Got: {result}")
    
    print(f"\nResults: {passed}/{passed + failed} passed")
    return failed == 0
 
 
# Test the standard implementation
def search_with_duplicates(nums, target):
    if not nums:
        return False
    
    low, high = 0, len(nums) - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        if nums[mid] == target:
            return True
        
        if nums[low] == nums[mid] == nums[high]:
            low += 1
            high -= 1
            continue
        
        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
    
    return False
 
 
test_duplicate_edge_cases(search_with_duplicates)

Interview Discussion Points

When discussing this problem with an interviewer, several points can demonstrate deep understanding and mature engineering judgment.

Points to Raise in Interviews

•Ask about duplicates first: 'Are there duplicate values in the array?' This immediately shows you know about the complexity difference.
•Explain the limitation: 'With duplicates, we can't guarantee O(log n) in the worst case because we might not be able to determine which half is sorted.'
•Justify your approach: 'I'm incrementing low and decrementing high because when all boundary values are equal, we have no information to make a larger elimination.'
•Discuss real-world implications: 'In practice, if we expect limited duplicates, the average case is still O(log n). The worst case only occurs with adversarial or highly degenerate inputs.'
•Mention alternatives: 'If duplicates are common and we're doing many searches, preprocessing into a hash set might be more practical.'
•Trade-off discussion: 'We could also just do linear search—it has the same worst-case complexity but simpler code and lower constant factors for small arrays.'

The Meta-Skill

What interviewers really want to see is that you understand why the problem becomes harder with duplicates, not just that you can write the code. The ability to analyze and explain algorithmic limitations is more valuable than memorizing solutions.

Weak Interview Response

•'I'll just check if values are equal and skip'
•'It's O(log n)... I think'
•'I memorized this from LeetCode'
•No mention of why duplicates matter
•No discussion of alternatives

Strong Interview Response

•'Duplicates break the invariant because...'
•'Average case O(log n), worst case O(n), and here's why...'
•'The fundamental limitation is information-theoretic'
•Asks clarifying questions about input constraints
•Discusses practical trade-offs

Summary: Handling the Challenging Extension

Handling duplicates in rotated sorted arrays is a significant extension that tests deep understanding of binary search invariants. Here's what we covered:

Key Takeaways

•Duplicates break the key invariant: When nums[low] = nums[mid] = nums[high], we cannot determine which half is sorted.
•The fix is simple but has complexity implications: Shrink the search space by one on each end when ambiguous, then retry.
•Worst case becomes O(n): This is fundamental, not a fixable deficiency. When all boundary values are equal, no comparison-based algorithm can do better.
•Average case is still O(log n): If duplicates are limited, the algorithm remains efficient in practice.
•Alternative approaches exist: Hash sets for existence, two-pass (find pivot then search), or accepting linear search for small arrays.
•Interview insight matters: Understanding WHY duplicates are hard is more valuable than memorizing the code.

What's next:

We've covered the algorithm variations in detail. The next page provides a comprehensive time complexity analysis across all scenarios—rotated vs non-rotated, with vs without duplicates, and best/average/worst cases for each.

Page Complete

You now understand how to handle duplicates in rotated sorted arrays, including why the complexity degrades and how to explain this in interviews. This is one of the more nuanced binary search variations, and mastering it demonstrates genuine algorithmic maturity.

3 / 4

Loading learning content...

Data Structures & AlgorithmsSearch in Rotated Arrays

Search in Rotated Arrays

LevelIntermediate

Duration60 mins

TopicSearch in Rotated Arrays

3 / 4

Handling Duplicates in Rotated Arrays

When Duplicates Break Everything

Duplicates shatter this assumption.

The Worst-Case Reality

What You Will Learn

Why Duplicates Break the Algorithm

Let's understand precisely why duplicates cause problems. The key check in our algorithm is:

if nums[low] <= nums[mid]:  # Left half is sorted

With distinct elements, this check is reliable:

If nums[low] <= nums[mid], the elements from low to mid are in ascending order
If nums[low] > nums[mid], the rotation point is in the left half

With duplicates, the check becomes ambiguous:

Consider [2, 2, 2, 3, 1, 2, 2]. Here:

nums[0] = 2, nums[3] = 3, nums[6] = 2
Rotation point is between index 3 and 4 (between 3 and 1)
Check: nums[0] <= nums[3]? Is 2 <= 3? Yes.
Conclusion: Left half [2, 2, 2, 3] is sorted. ✓ Correct!

But now consider [1, 1, 1, 1, 1, 2, 1, 1, 1]:

nums[0] = 1, nums[4] = 1, nums[8] = 1
Rotation point is between index 5 and 6 (between 2 and 1)
Check: nums[0] <= nums[4]? Is 1 <= 1? Yes.
Conclusion: Left half is sorted?

The Pathological CaseWhen all boundary values are identical, we have zero information.

Input

nums = [1, 1, 1, 1, 1, 2, 1, 1, 1], target = 2

Output

low = 0, mid = 4, high = 8
nums[0] = 1, nums[4] = 1, nums[8] = 1

Check: nums[low] <= nums[mid]?
       1 <= 1? YES

Conclusion: Left half should be sorted.

But wait! The actual values are:
Left half:  [1, 1, 1, 1, 1] - Sorted ✓
Right half: [1, 2, 1, 1, 1] - Contains the rotation!

If we assume left half is sorted and target=2 is not in [1,1],
we'd search right half → Happens to be correct by luck.

Now try: nums = [2, 1, 1, 1, 1, 1, 1, 1, 1], target = 1
mid = 4, nums[0]=2, nums[4]=1
Check: nums[0] <= nums[4]? 2 <= 1? NO
So right half should be sorted...

Right half: [1, 1, 1, 1, 1] - Sorted ✓
Left half: [2, 1, 1, 1] - Contains rotation ✓

Correct again! But...

Explanation

The critical case is when nums[low] = nums[mid] = nums[high]. We genuinely cannot determine which half is sorted.

The Unbreakable Ambiguity

The Modified Algorithm for Duplicates

The strategy:

If nums[low] = nums[mid] = nums[high], we cannot determine which half is sorted
In this case, increment low and decrement high (skip the duplicate boundaries)
Continue with the standard algorithm

This handles ambiguity at the cost of occasionally making O(1) progress instead of halving.

Converting Mermaid diagram...

search_rotated_duplicates.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
def search_with_duplicates(nums: list[int], target: int) -> bool:
    """
    Search for target in a rotated sorted array that MAY contain duplicates.
    
    NOTE: Returns bool (existence), not index, because duplicates make
    index less meaningful and this matches LeetCode's problem formulation.
    
    Args:
        nums: A rotated sorted array possibly with duplicates
        target: The value to search for
        
    Returns:
        True if target exists in the array, False otherwise
        
    Time Complexity: O(log n) average, O(n) worst case
    Space Complexity: O(1)
    
    The worst case happens when most/all elements are the same except one.
    Example: [1,1,1,1,1,2,1,1,1] - we may need to check almost every element.
    """
    if not nums:
        return False
    
    low, high = 0, len(nums) - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        # Found the target
        if nums[mid] == target:
            return True
        
        # CRITICAL: Handle the ambiguous case
        # When nums[low] = nums[mid] = nums[high], we cannot determine
        # which half is sorted. We must shrink the search space manually.
        if nums[low] == nums[mid] == nums[high]:
            low += 1
            high -= 1
            continue  # Re-evaluate with smaller range
        
        # Now we can apply the standard logic
        # At least one of the inequalities must be strict
        
        if nums[low] <= nums[mid]:
            # Left half is sorted
            if nums[low] <= target < nums[mid]:
                high = mid - 1  # Target in sorted left half
            else:
                low = mid + 1  # Target in right half
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[high]:
                low = mid + 1  # Target in sorted right half
            else:
                high = mid - 1  # Target in left half
    
    return False
 
 
def search_with_duplicates_verbose(nums: list[int], target: int) -> bool:
    """Same algorithm with detailed tracing."""
    if not nums:
        return False
    
    low, high = 0, len(nums) - 1
    iteration = 0
    
    print(f"Searching for {target} in {nums}")
    print("=" * 70)
    
    while low <= high:
        mid = low + (high - low) // 2
        iteration += 1
        
        print(f"\nIteration {iteration}: low={low}, mid={mid}, high={high}")
        print(f"  Values: nums[{low}]={nums[low]}, nums[{mid}]={nums[mid]}, nums[{high}]={nums[high]}")
        
        if nums[mid] == target:
            print(f"  ✓ FOUND! Target {target} at index {mid}")
            return True
        
        if nums[low] == nums[mid] == nums[high]:
            print(f"  ⚠️ AMBIGUOUS: All boundary values = {nums[low]}")
            print(f"  Cannot determine sorted half, shrinking by 1 each side")
            low += 1
            high -= 1
            continue
        
        if nums[low] <= nums[mid]:
            print(f"  Left half sorted: [{nums[low]}...{nums[mid]}]")
            if nums[low] <= target < nums[mid]:
                print(f"  Target in sorted left half")
                high = mid - 1
            else:
                print(f"  Target NOT in sorted left half")
                low = mid + 1
        else:
            print(f"  Right half sorted: [{nums[mid]}...{nums[high]}]")
            if nums[mid] < target <= nums[high]:
                print(f"  Target in sorted right half")
                low = mid + 1
            else:
                print(f"  Target NOT in sorted right half")
                high = mid - 1
    
    print(f"\n✗ NOT FOUND after {iteration} iterations")
    return False
 
 
# Demonstrations
if __name__ == "__main__":
    print("\n" + "=" * 70)
    print("TEST 1: Duplicates but no ambiguity")
    print("=" * 70)
    search_with_duplicates_verbose([2, 5, 6, 0, 0, 1, 2], 0)
    
    print("\n" + "=" * 70)
    print("TEST 2: Pathological case - many duplicates")
    print("=" * 70)
    search_with_duplicates_verbose([1, 1, 1, 1, 1, 2, 1, 1, 1], 2)
    
    print("\n" + "=" * 70)
    print("TEST 3: All same values - target not present")
    print("=" * 70)
    search_with_duplicates_verbose([1, 1, 1, 1, 1], 2)
    
    print("\n" + "=" * 70)
    print("TEST 4: Worst case - degenerate to linear")
    print("=" * 70)
    arr = [1] * 100 + [2] + [1] * 100  # 201 elements, mostly 1s
    print(f"Array of 201 elements (mostly 1s), searching for 2")
    result = search_with_duplicates(arr, 2)
    print(f"Result: {result}")

Complexity Analysis with Duplicates

Understanding the complexity behavior is crucial for interview discussions. Let's analyze both average and worst cases.

Complexity Comparison: Distinct vs Duplicate Elements
Scenario	Distinct Elements	With Duplicates
Best Case	O(1) - target at mid	O(1) - target at mid
Average Case	O(log n)	O(log n) - if duplicates are limited
Worst Case	O(log n)	O(n) - when nums[low]=nums[mid]=nums[high]
Space	O(1)	O(1)

Why O(n) worst case?

In the worst case with duplicates, every iteration might only eliminate 2 elements (one from each end). Consider searching for 0 in:

[1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]

At each step:

nums[low] = 1, nums[mid] = 1, nums[high] = 1
We increment low and decrement high
We eliminate 2 elements per iteration

For an array of n elements, we need approximately n/2 iterations = O(n).

Can we do better?

Interview Insight

Average case analysis:

If duplicates are sparse (most elements are distinct), the algorithm still performs close to O(log n) because:

The ambiguous case (nums[low] = nums[mid] = nums[high]) occurs rarely
Most iterations still halve the search space
Only occasional O(1) reductions don't significantly impact overall logarithmic behavior

In practice, if you expect limited duplicates, this algorithm remains efficient. Only in adversarial or highly degenerate inputs does it approach O(n).

Alternative Approaches and Trade-offs

Given the limitations with duplicates, are there alternative strategies? Let's examine several approaches and their trade-offs.

Alternative Strategies

•
Approach 1: Skip duplicates aggressively Instead of just low++, high--, skip all duplicates at the boundaries:
```
while low < high and nums[low] == nums[low+1]: low += 1
while low < high and nums[high] == nums[high-1]: high -= 1
```
This can help in some cases but doesn't change worst-case complexity. If ALL elements are the same except one, we still need O(n).
•
Approach 2: Find pivot first, then binary search First find the rotation point (minimum element), then do standard binary search on the appropriate sorted half.
- Pro: Separates concerns
- Con: Still O(n) worst case for finding pivot with duplicates
- Con: Two passes instead of one
•
Approach 3: Hash set for existence check If you only need existence (not index), preprocess into a hash set:
- Pro: O(1) lookup after O(n) preprocessing
- Con: O(n) extra space
- Con: Not useful for single queries
This is worth mentioning if the interviewer values practical thinking.
•
Approach 4: Accept linear search If duplicates are expected and array is small, a simple linear search is:
- Simpler to implement
- Same worst-case complexity
- Lower constant factors (no repeated comparisons)
For arrays under ~1000 elements with many duplicates, linear search might actually be faster!

alternative_approaches.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# Alternative 1: Aggressive duplicate skipping
def search_skip_duplicates(nums: list[int], target: int) -> bool:
    """Skip runs of duplicates at boundaries."""
    if not nums:
        return False
    
    low, high = 0, len(nums) - 1
    
    while low <= high:
        # Skip duplicates at low end
        while low < high and nums[low] == nums[low + 1]:
            low += 1
        
        # Skip duplicates at high end
        while low < high and nums[high] == nums[high - 1]:
            high -= 1
        
        mid = low + (high - low) // 2
        
        if nums[mid] == target:
            return True
        
        # Now apply standard logic (less likely to hit ambiguous case)
        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
    
    return False
 
 
# Alternative 2: Find pivot first, then search
def find_rotation_index_with_dups(nums: list[int]) -> int:
    """Find index of minimum element (rotation point)."""
    low, high = 0, len(nums) - 1
    
    while low < high:
        mid = low + (high - low) // 2
        
        if nums[mid] > nums[high]:
            low = mid + 1
        elif nums[mid] < nums[high]:
            high = mid
        else:
            # nums[mid] == nums[high], can't decide
            high -= 1
    
    return low
 
 
def search_two_pass(nums: list[int], target: int) -> bool:
    """Find pivot, then binary search appropriate half."""
    if not nums:
        return False
    
    pivot = find_rotation_index_with_dups(nums)
    n = len(nums)
    
    # Standard binary search, adjusted for rotation
    low, high = 0, n - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        real_mid = (mid + pivot) % n  # Adjust for rotation
        
        if nums[real_mid] == target:
            return True
        elif nums[real_mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return False
 
 
# Compare approaches
def compare_approaches():
    test_cases = [
        ([2, 5, 6, 0, 0, 1, 2], 0),
        ([1, 1, 1, 1, 1, 2, 1, 1, 1], 2),
        ([1, 1, 1, 1, 1], 2),
        ([3, 1, 1], 3),
    ]
    
    print("Comparing Approaches")
    print("=" * 60)
    
    for arr, target in test_cases:
        result1 = search_skip_duplicates(arr, target)
        result2 = search_two_pass(arr, target)
        
        print(f"Array: {arr}, Target: {target}")
        print(f"  Skip duplicates: {result1}")
        print(f"  Two-pass: {result2}")
        print()
 
 
compare_approaches()

Edge Cases Specific to Duplicates

Duplicates introduce several edge cases that don't exist with distinct elements. Understanding these is crucial for a robust implementation.

Duplicate-Specific Edge Cases

•All elements identical: [1, 1, 1, 1, 1] — Returns true if target=1, false otherwise. Algorithm degrades to O(n) but is correct.
•Two distinct values, many duplicates: [1, 1, 1, 2, 2, 2] — Rotation can be anywhere between blocks. Handle boundary carefully.
•Duplicates at rotation point: [2, 2, 1, 1] — The rotation point separates the two duplicate blocks. Our algorithm handles this.
•Target equals boundary duplicates: [1, 1, 1, 2, 1, 1, 1], target=1 — Must search both halves because target appears in both.
•Single non-duplicate: [1, 1, 1, 2, 1, 1, 1], target=2 — The unique element is the target. May need to search through duplicates to find it.
•Rotation at different points in duplicate runs: [1, 1, 2, 1, 1] vs [1, 2, 1, 1, 1] — Same elements, different rotations. Both handled correctly.

duplicate_edge_cases_test.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
def test_duplicate_edge_cases(search_fn):
    """Comprehensive test suite for duplicate handling."""
    
    test_cases = [
        # (array, target, expected, description)
        ([1, 1, 1, 1, 1], 1, True, "All same - target present"),
        ([1, 1, 1, 1, 1], 2, False, "All same - target absent"),
        ([2, 2, 2, 0, 1], 0, True, "Rotation amid duplicates"),
        ([2, 2, 2, 0, 2], 0, True, "Target in rotation gap"),
        ([1, 1, 1, 2, 1, 1, 1], 2, True, "Single non-duplicate target"),
        ([1, 1, 1, 2, 1, 1, 1], 1, True, "Target in duplicate regions"),
        ([1, 1, 1, 2, 1, 1, 1], 3, False, "Target not present"),
        ([3, 1, 1], 3, True, "Minimum duplicates, target at start"),
        ([1, 1, 3], 3, True, "Minimum duplicates, target at end"),
        ([1, 1, 1, 2, 2, 2, 1, 1, 1], 2, True, "Block of different value"),
        ([2, 2, 2, 1, 1, 1, 2, 2, 2], 1, True, "Block in middle"),
        ([2, 2, 1, 2, 2], 1, True, "Single different value in middle"),
        ([], 1, False, "Empty array"),
        ([1], 1, True, "Single element - present"),
        ([1], 0, False, "Single element - absent"),
    ]
    
    print("Testing Duplicate Edge Cases")
    print("=" * 70)
    
    passed = failed = 0
    
    for arr, target, expected, desc in test_cases:
        result = search_fn(arr, target)
        status = "✓" if result == expected else "✗"
        
        if result == expected:
            passed += 1
        else:
            failed += 1
            print(f"{status} FAIL: {desc}")
            print(f"    Array: {arr}, Target: {target}")
            print(f"    Expected: {expected}, Got: {result}")
    
    print(f"\nResults: {passed}/{passed + failed} passed")
    return failed == 0
 
 
# Test the standard implementation
def search_with_duplicates(nums, target):
    if not nums:
        return False
    
    low, high = 0, len(nums) - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        if nums[mid] == target:
            return True
        
        if nums[low] == nums[mid] == nums[high]:
            low += 1
            high -= 1
            continue
        
        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
    
    return False
 
 
test_duplicate_edge_cases(search_with_duplicates)

Interview Discussion Points

When discussing this problem with an interviewer, several points can demonstrate deep understanding and mature engineering judgment.

Points to Raise in Interviews

•Ask about duplicates first: 'Are there duplicate values in the array?' This immediately shows you know about the complexity difference.
•Explain the limitation: 'With duplicates, we can't guarantee O(log n) in the worst case because we might not be able to determine which half is sorted.'
•Justify your approach: 'I'm incrementing low and decrementing high because when all boundary values are equal, we have no information to make a larger elimination.'
•Discuss real-world implications: 'In practice, if we expect limited duplicates, the average case is still O(log n). The worst case only occurs with adversarial or highly degenerate inputs.'
•Mention alternatives: 'If duplicates are common and we're doing many searches, preprocessing into a hash set might be more practical.'
•Trade-off discussion: 'We could also just do linear search—it has the same worst-case complexity but simpler code and lower constant factors for small arrays.'

The Meta-Skill

Weak Interview Response

•'I'll just check if values are equal and skip'
•'It's O(log n)... I think'
•'I memorized this from LeetCode'
•No mention of why duplicates matter
•No discussion of alternatives

Strong Interview Response

•'Duplicates break the invariant because...'
•'Average case O(log n), worst case O(n), and here's why...'
•'The fundamental limitation is information-theoretic'
•Asks clarifying questions about input constraints
•Discusses practical trade-offs

Summary: Handling the Challenging Extension

Handling duplicates in rotated sorted arrays is a significant extension that tests deep understanding of binary search invariants. Here's what we covered:

Key Takeaways

•Duplicates break the key invariant: When nums[low] = nums[mid] = nums[high], we cannot determine which half is sorted.
•The fix is simple but has complexity implications: Shrink the search space by one on each end when ambiguous, then retry.
•Worst case becomes O(n): This is fundamental, not a fixable deficiency. When all boundary values are equal, no comparison-based algorithm can do better.
•Average case is still O(log n): If duplicates are limited, the algorithm remains efficient in practice.
•Alternative approaches exist: Hash sets for existence, two-pass (find pivot then search), or accepting linear search for small arrays.
•Interview insight matters: Understanding WHY duplicates are hard is more valuable than memorizing the code.

What's next:

Page Complete

3 / 4