DSA interview question

Search in a Rotated Sorted Array II (With Duplicates)

Medium · Algorithms · Topics: binary search, rotated array

The problem

The circular log buffer from the previous problem now allows repeated IDs (retries reuse the same ID), so an array might look like [2, 5, 6, 0, 0, 1, 2]. The question is just whether a given ID is present. The "one half is always sorted" trick still works, except in one ambiguous situation: when nums[lo], nums[mid] and nums[hi] are all equal, you can't tell which side holds the rotation. The fix is to discard both ends and continue, which costs O(n) in the worst case but stays O(log n) whenever duplicates don't get in the way.

Example: [2, 5, 6, 0, 0, 1, 2], target 0 → true.

Function signature

bool searchRotatedWithDuplicates(const vector<int>& nums, int target);

Test cases

Input `(nums, target)`	Output	Explanation
`([2, 5, 6, 0, 0, 1, 2], 0)`	true
`([2, 5, 6, 0, 0, 1, 2], 3)`	false
`([1, 0, 1, 1, 1], 0)`	true	lo, mid and hi are all 1 at first
`([1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, 1, 1], 13)`	true	Needs the shrink-both-ends step
`([1], 0)`	false
`([3, 1], 1)`	true

(Confirm: the array is a rotation of a non-decreasing array; duplicates are allowed; return whether the target exists.)

How interviewers phrase it

"Search in a rotated sorted array that may contain duplicates" (LeetCode 81).
Almost always a follow-up to the distinct-values version: "What changes if duplicates are allowed?"

Clarifying questions to ask

Can there be duplicates? (That's the whole point here.)
Return a boolean or an index?
Is O(log n) expected in the worst case? (It isn't achievable.)

Follow-ups to expect

"Why can't you tell which half is sorted?"
"What do you do then?"
"What's the worst-case complexity?"
"What's the average case?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview