Search in Rotated Sorted Array II

Search in Rotated Sorted Array II

What is this problem about?

The Search in Rotated Sorted Array II interview question extends the first version by allowing duplicate values in the rotated sorted array. Given such an array and a target, return true if the target exists. Duplicates make it impossible to always determine which half is sorted, requiring a fallback that degrades worst-case complexity to O(n) but maintains O(log n) average case.

Why is this asked in interviews?

Apple, Cisco, Uber, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this problem because it tests whether candidates understand the limitation duplicates impose on binary search correctness. The fallback (left++) when nums[left] == nums[mid] == nums[right] is the key insight. This models real-world scenarios where data streams may have repeated timestamps or sorted logs with duplicate entries.

Algorithmic pattern used

The pattern is modified binary search with a duplicate-handling fallback. The algorithm mirrors Search in Rotated Sorted Array I, but adds: when nums[left] == nums[mid], we cannot determine which half is sorted. In this case, increment left (safely discard one duplicate from the left) and continue. This worst-case O(n) step is necessary only when the leftmost element equals the mid element.

Example explanation

Array: [2, 5, 6, 0, 0, 1, 2], target = 0.

• left=0, right=6, mid=3. nums[0]=2, nums[3]=0. nums[0] > nums[3] → right half sorted: [0,1,2]. 0 in [0,2] → search right. left=3.
• left=3, right=6, mid=4. nums[3]=0, nums[4]=0. nums[3]=nums[4] and left==right... nums[3] ≤ nums[4] → left sorted: [0,0]. 0 in [0,0] → search left. right=3.
• nums[3]=0 = target → true.

Duplicate fallback: [1,1,1,3,1], target=3.

• mid=2: nums[0]=1=nums[2]=1. Can't determine sorted half → left++. Continue until unambiguous.

Common mistakes candidates make

• Forgetting the duplicate fallback entirely, causing the algorithm to give wrong answers.
• Incrementing right instead of left for the fallback — only left++ is safe.
• Applying the same logic as the no-duplicate version without the extra condition.
• Not testing on arrays like [1,1,1,1,1,1] where the fallback is triggered at every step.

Interview preparation tip

For the Search in Rotated Sorted Array II coding problem, the binary search array interview pattern extends with one key addition: handle nums[left] == nums[mid] by incrementing left. Know that this makes worst-case O(n) — be ready to explain this tradeoff to interviewers at Glassdoor and Walmart Labs. The distinction between versions I and II is often the follow-up: "what changes when duplicates are allowed?"