Skip to main content

65. Search in Rotated Sorted Array II

mediumAsked at Ola

Search for a target in a rotated sorted array that may contain duplicates.

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

Problem

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values). It is then rotated at an unknown pivot. Given the array after rotation and a target value, return true if target is in nums and false otherwise.

Constraints

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 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

Iterate and compare.

Time
O(n)
Space
O(1)
return nums.includes(target);

Tradeoff:

2. Binary search with duplicate skip

Binary search, but when nums[lo]==nums[mid]==nums[hi] you can only safely shrink both ends by one.

Time
O(log n) avg, 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:

Ola-specific tips

Ola interviewers want you to articulate the worst-case duplicate skip explicitly; tie it to dedup-tolerant searches over rotated dispatch logs.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →