Shubham Sourabhthe room · director's cutplain résumé
Room 04 · The Grind — Binary Search

Search In Rotated Sorted Array II

MEDIUM✓ CHIP-TIMEDLC #81 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Same rotated-array search as before, but duplicate values are now allowed — decide only whether the target exists, since duplicates make returning a single index ambiguous.

This is the same rotated-array hunt as before, except duplicate values are now allowed to appear anywhere in the array, which quietly breaks some of the tricks that worked when every value was distinct.

A target value arrives with the array, and the only question worth answering is whether that value exists somewhere inside it — with duplicates around, a single matching index would be ambiguous anyway, so existence is all that's asked.

Repeated values can make the two endpoints and the midpoint of a search window all look identical, which hides which half of the window is actually the sorted one — the drill has to account for that blind spot.

  • array holds up to a few thousand values, duplicates allowed
  • array may be rotated by any amount, including not at all
  • only a true/false existence answer is expected, no index
  • worst case with heavy duplication can degrade toward a full scan
EX 01
nums = [2, 3, 3, 4, 1, 1] · target = 3
→ true
duplicate values, hit
EX 02
nums = [2, 3, 3, 4, 1, 1] · target = 5
→ false
duplicate values, absent target
EX 03
nums = [1, 1, 1, 1, 1, 1, 2] · target = 2
→ true
heavy duplicates, target at the very end

The hintstake only what you need

HINT 1 THE NUDGE

Duplicates can make nums[lo], nums[mid], and nums[hi] all equal, which breaks the trick of telling which half is sorted by comparing endpoints — what's the safe fallback when that comparison is uninformative?

HINT 2 THE STRUCTURE

When nums[lo] == nums[mid] == nums[hi], you can't tell which side is sorted — just shrink the window by one from each end and keep going; you lose at most O(1) work per collision.

HINT 3 ONE STEP FROM THE ANSWER

Otherwise, run the same sorted-half test as the distinct-values version: whichever side is strictly ordered end-to-end tells you where to look, and where to discard.

Coach's boardthe pattern, step by step

THE TIE BREAKERPATTERN · MODIFIED BINARY SEARCH + SKIP TIESnums = [1, 1, 1, 1, 0, 1, 1] · target = 0
1
1
1
1
0
1
1
STEP 1

Target 0, and duplicates are everywhere — the usual sorted-half trick can get confused when the edges tie with the middle.

STEP 1 / 9 · ← → WORK TOO

The splitstwo paces, two languages

grind/search-in-rotated-sorted-array-ii.py — RACE PACE
LANG ▸
PACE ▸
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return True
            if nums[lo] == nums[mid] == nums[hi]:
                lo += 1
                hi -= 1
            elif nums[lo] <= nums[mid]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return False
TIME O(N) WORST CASE, O(LOG N) AVERAGESPACE O(1)PYTHON · RACE PACE · 21 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED