Skip to main content

65. Search in Rotated Sorted Array II

mediumAsked at Snowflake

Search in a rotated sorted array with duplicates allowed. Snowflake uses this to highlight how duplicates degrade binary search — the same concern when a clustering key is low-cardinality and pruning effectiveness drops.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake storage-team uses this in onsites to discuss low-cardinality clustering keys.
  • LeetCode Discuss (2025-10)— Reported at Snowflake SDE-I screens.

Problem

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values). Prior to being passed to your function, nums is possibly rotated. Given the array nums after the possible rotation and an integer target, return true if target is in nums, or false otherwise.

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 the whole array. Simple and worst-case correct.

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

Tradeoff: Defeats the purpose. Mention only as the fallback.

2. Modified binary search with skip-equal (optimal in expectation)

Like LC 33, but when nums[lo] == nums[mid] == nums[hi], the sorted-half invariant fails — inch lo and hi inward.

Time
O(log n) average, O(n) worst case
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). The 'all three equal' case forces O(n) worst case — e.g., on [1,1,1,1,...,1,2,1,...].

Snowflake-specific tips

Snowflake interviewers want you to articulate why duplicates break the invariant — when nums[lo] == nums[mid] you can't tell which half is sorted. Bonus signal: pivot to low-cardinality clustering keys, where Snowflake's micro-partition pruning degrades when many partitions share the same value range.

Common mistakes

  • Not handling the 'all three equal' case, leading to infinite loops on certain inputs.
  • Using strict < on the boundary comparison, missing equality.
  • Trying to find pivot first via binary search — duplicates make this O(n) too.

Follow-up questions

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

  • Find Minimum in Rotated Sorted Array II (LC 154).
  • How does Snowflake's pruning degrade with low cardinality?
  • When does the planner pick full-scan over pruning?

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 is worst case O(n)?

When nums[lo] == nums[mid] == nums[hi], we can only inch the boundaries — no halving. An adversarial input forces n/2 iterations.

How does this relate to clustering keys?

If a clustering key has few distinct values, many partitions share the same [min, max]. Pruning a predicate to specific partitions becomes ineffective — analogous to how duplicates kill binary search here.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →