Skip to main content

61. Search in Rotated Sorted Array II

mediumAsked at Vercel

Search a target in a rotated sorted array WITH duplicates. Vercel asks this for the worst-case O(n) reasoning — when duplicates break the 'one half is sorted' invariant.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-12)— Vercel platform onsite; worst-case analysis expected.
  • Blind (2026-Q1)— Listed in Vercel screen pool.

Problem

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values). Before being passed, 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.

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

Tradeoff: Works; with duplicates, it's actually the same big-O as the binary-search variant (worst case).

2. Modified binary search with duplicate-skip (optimal expected)

Same as LC 33, but when nums[lo] == nums[mid] == nums[hi] we can't tell which half is sorted, so increment lo and decrement hi by 1.

Time
O(n) worst case, O(log n) average
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--;
    } else 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: Average O(log n), worst case O(n) when many duplicates. The duplicate-skip case (lo++ hi--) is necessary because identical endpoints leave the sorted-half check ambiguous.

Vercel-specific tips

Vercel grades the analysis of WHEN binary search degrades and why. Bonus signal: explicitly stating worst-case O(n) (e.g., all 1s with one 2 hidden) and explaining that this is unavoidable when duplicates allow the endpoints and middle to all match.

Common mistakes

  • Treating it the same as LC 33 — fails on inputs like [1,1,1,1,2,1,1].
  • Decrementing hi without also incrementing lo — wastes one step instead of two.
  • Claiming O(log n) — not true in the worst case.

Follow-up questions

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

  • Find Minimum in Rotated Sorted Array II (LC 154) — same duplicate problem.
  • Why isn't there a true O(log n) algorithm with duplicates?
  • Search in a doubly-rotated array.

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?

When nums[lo], nums[mid], nums[hi] are all equal, we can't tell which half is sorted. The lo++ hi-- step makes only constant progress. In the worst case, all elements are equal except one, and we walk linearly.

Is there a faster algorithm?

No. Any comparison-based algorithm on a rotated sorted array with duplicates needs at least Omega(n) in the worst case — you can construct adversarial inputs.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →