Skip to main content

62. Search in Rotated Sorted Array II

mediumAsked at Plaid

Search a rotated sorted array that may contain duplicates. Plaid asks this as a binary-search-with-ambiguity problem — exactly the shape they face when a circular log has duplicate-event timestamps.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • LeetCode Discuss (2026)— Plaid SWE II OA.
  • Glassdoor (2025)— Plaid backend OA — variant.

Problem

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values). Before being passed to your function, nums is rotated at an unknown pivot index. Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

Constraints

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • nums is guaranteed to be rotated at some pivot.
  • -10^4 <= target <= 10^4

Examples

Example 1

Input
nums = [2,5,6,0,0,1,2], target = 0
Output
true

Example 2

Input
nums = [2,5,6,0,0,1,2], target = 3
Output
false

Approaches

1. Linear scan

Walk and check each.

Time
O(n)
Space
O(1)
function search(nums, target) {
  return nums.includes(target);
}

Tradeoff: Worst-case correct. Misses the binary-search optimization on average.

2. Modified binary search with duplicate handling

Same as LC 33 but when nums[lo] == nums[mid] == nums[hi], we can't tell which half is sorted — shrink lo and hi by one and continue.

Time
O(log n) average, O(n) worst
Space
O(1)
function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) return true;
    if (nums[lo] === nums[mid] && nums[mid] === nums[hi]) { lo++; hi--; continue; }
    if (nums[lo] <= nums[mid]) {
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return false;
}

Tradeoff: Logarithmic on average. Degenerates to linear when the array is mostly duplicates (e.g., [1,1,1,1,...,1,2,1,...,1]).

Plaid-specific tips

Plaid grades this on whether you spot the duplicate-ambiguity case and resolve it correctly. Bonus signal: state out loud 'when both endpoints equal the midpoint, we can't tell which half is sorted, so we shrink the search space by one.' Connect to deduplicated log lookup where timestamps may repeat under high throughput.

Common mistakes

  • Forgetting the lo++/hi-- in the duplicate case — infinite loop.
  • Not returning early on nums[mid] === target.
  • Treating duplicates as a binary-search failure — they only force one extra step.

Follow-up questions

An interviewer at Plaid may pivot to one of these next:

  • Find minimum in rotated array with duplicates (LC 154).
  • Return all indices of target.
  • Worst-case-O(log n) variant — not possible with full duplicates.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why O(n) worst case?

An array like [1,1,1,1,1,0,1,1,1] looks the same at lo, mid, and hi. We can only eliminate one element per step in that case.

Why not always do linear scan?

On average (random duplicates), the binary search still wins. The pathological worst case is rare in practice.

Practice these live with InterviewChamp.AI

Drill Search in Rotated Sorted Array II and other Plaid interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →