Log inSign up
mediumLeetCodeNot Started

Search in Rotated Sorted Array II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).

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.

You must decrease the overall operation steps as much as possible.

Example 1 · Target Present with Duplicates:

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 0
Output: true
Explanation: 0 is located at index 3.

Example 2 · Target Not Present:

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3
Output: false
Explanation: 3 is not present in nums.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Search in Rotated Sorted Array I (without duplicates)
  • Standard Binary Search boundary invariants

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Handle duplicate values in rotated binary search correctly.
  • Formulate safe low++ and high-- pruning logic.
  • Understand the theoretical limit that forces O(N) worst-case in the presence of duplicates.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If nums[mid] == target -> return true.
  • If nums[low] == nums[mid] == nums[high] -> low++, high--.
  • Else if nums[low] <= nums[mid] (left sorted) -> test if target in [nums[low], nums[mid]).
  • Else (right sorted) -> test if target in (nums[mid], nums[high]].

Connected Patterns:

Find Minimum in Rotated Sorted Array IISearch in Rotated Sorted Array I

1. Linear Scan (Brute Force)

Intuition

Since duplicates in a rotated sorted array degrade the worst-case binary search to O(n), a straightforward linear scan checks every element in O(n) time and O(1) space.

When to apply: Use as the baseline reference comparison for search correctness.

Linear Scan (O(N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Examine the first slot
Visual state
Values and pointers at this exact step
pointers
S
2
5
6
0
0
1
2
0
↑ i
1
2
3
4
5
6
Variables at this step
i
0
currentVal
2
target
3
found
false
Check / comparison
Compare nums[0] (2) with target (3)
Decision / next transition
2 != 3. Advance pointer i to 1.
Why this step matters

Examine the first slot. Value 2 is not the target.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public boolean search(int[] nums, int target) {
4 for (int x : nums) {
5 if (x == target) return true;
6 }
7 return false;
8 }
9 }
10
11 public static void main(String[] args) {
12 Solution sol = new Solution();
13 int[] nums = {2, 5, 6, 0, 0, 1, 2};
14 int target = 0;
15 System.out.println("Search Result: " + sol.search(nums, target));
16 }
17}

Time & Space Complexity

  • Time complexity: O(n) — A single linear pass inspects up to n elements.
  • Space complexity: O(1) — O(1) auxiliary variables.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Two-Pointer Inward Shrink (Better)

Intuition

Initialize low = 0 and high = n - 1. In each step check nums[low] == target or nums[high] == target. If either matches, return true. Otherwise advance low++ and high--. Terminates in n/2 steps.

When to apply: Use when demonstrating symmetric bidirectional search.

Standard Rotated Binary Search (Duplicate-Unaware)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Right half is sorted
Visual state
Values and pointers at this exact step
pointers
S
2
5
6
0
0
1
2
0
↑ low
1
2
3
↑ mid
4
5
6
↑ high
Variables at this step
low
0
mid
3
high
6
target
3
Check / comparison
low = 0, high = 6 -> mid = 3. nums[mid] = 0. Compare with target 3
Decision / next transition
nums[mid] (0) != 3. Inspect right half [0, 0, 1, 2]: nums[mid] <= nums[high] (0 <= 2).
Why this step matters

Right half is sorted. Does target 3 lie in (0, 2]? No, 3 > 2. Therefore discard right half, set high = mid - 1 = 2.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public boolean search(int[] nums, int target) {
4 int low = 0, high = nums.length - 1;
5 while (low <= high) {
6 if (nums[low] == target || nums[high] == target) return true;
7 low++;
8 high--;
9 }
10 return false;
11 }
12 }
13
14 public static void main(String[] args) {
15 Solution sol = new Solution();
16 int[] nums = {2, 5, 6, 0, 0, 1, 2};
17 int target = 0;
18 System.out.println("Search Result: " + sol.search(nums, target));
19 }
20}

Time & Space Complexity

  • Time complexity: O(n) — Both pointers move towards each other, doing at most n/2 comparisons.
  • Space complexity: O(1) — O(1) memory for pointer variables.

3. Modified Binary Search with Duplicate Pruning (Optimal)

Intuition

1. If nums[mid] == target, return true. 2. When nums[low] == nums[mid] == nums[high], we cannot determine which half is sorted; increment low and decrement high. 3. If nums[low] <= nums[mid], the left half is sorted: if nums[low] <= target < nums[mid], search left; else search right. 4. Otherwise, the right half is sorted: if nums[mid] < target <= nums[high], search right; else search left.

When to apply: Use as the optimal standard interview solution for searching rotated sorted arrays with duplicates.

Rotated Binary Search with Duplicate Shrink (O(log N) Avg, O(N) Worst)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Target 3 is not in range (0, 2]
Visual state
Values and pointers at this exact step
pointers
S
2
5
6
0
0
1
2
0
↑ low
1
2
3
↑ mid
4
5
6
↑ high
Variables at this step
low
0
mid
3
high
6
target
3
Check / comparison
nums[low]=2, nums[mid]=0, nums[high]=2. nums[mid] != nums[low], so sorted half is decidable
Decision / next transition
Since nums[mid] (0) <= nums[high] (2), right half [0, 0, 1, 2] is sorted.
Why this step matters

Target 3 is not in range (0, 2]. Hence target must be in left half. Set high = mid - 1 = 2.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public boolean search(int[] nums, int target) {
4 int low = 0, high = nums.length - 1;
5 while (low <= high) {
6 int mid = low + (high - low) / 2;
7 if (nums[mid] == target) return true;
8
9 if (nums[low] == nums[mid] && nums[mid] == nums[high]) {
10 low++;
11 high--;
12 } else if (nums[low] <= nums[mid]) {
13 if (nums[low] <= target && target < nums[mid]) {
14 high = mid - 1;
15 } else {
16 low = mid + 1;
17 }
18 } else {
19 if (nums[mid] < target && target <= nums[high]) {
20 low = mid + 1;
21 } else {
22 high = mid - 1;
23 }
24 }
25 }
26 return false;
27 }
28 }
29
30 public static void main(String[] args) {
31 Solution sol = new Solution();
32 int[] nums = {2, 5, 6, 0, 0, 1, 2};
33 int target = 0;
34 System.out.println("Search Result: " + sol.search(nums, target));
35 }
36}

Time & Space Complexity

  • Time complexity: O(log n) average, O(n) worst case — On average, the search space halves each iteration (O(log n)). When all elements are identical and not equal to target, duplicate pruning takes O(n).
  • Space complexity: O(1) — O(1) auxiliary pointer variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear ScanO(N)O(1)Iterate through each element and return true if nums[i] == target.Inspects all elements sequentially.
2.Better — Find Pivot then Binary SearchO(N) worst, O(log N) averageO(1)Find rotation pivot using linear/modified search, then binary search the target half.Two-pass overhead.
3.Optimal — Direct Rotated Binary Search with Duplicate TrimOptimalO(log N) average, O(N) worst-caseO(1)Single-pass binary search with low++ / high-- boundary trimming when ambiguous.Worst-case all-duplicate array.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Search in Rotated Sorted Array II?

2.Why is the brute force approach suboptimal for large inputs in Search in Rotated Sorted Array II?

3.Which data structure or technique enables the optimal solution for Search in Rotated Sorted Array II?

Back to DSA Sheet