Log inSign up
hardLeetCodeNot Started

Find Minimum in Rotated Sorted Array II

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

Arrays
Solve on LeetCode
Lesson

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times.

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

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

Example 1 · Distinct Rotation with Duplicates:

Input: nums = [1, 3, 5]
Output: 1
Explanation: The original array was [1, 3, 5] and minimum is 1.

Example 2 · Array with Multiple Duplicates:

Input: nums = [2, 2, 2, 0, 1]
Output: 0
Explanation: The minimum element is 0 at index 3.

Example 3 · All Elements Equal Except One:

Input: nums = [3, 3, 1, 3]
Output: 1
Explanation: The minimum element is 1 at index 2.

Constraints:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums is sorted and rotated between 1 and n times.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Find Minimum in Rotated Sorted Array I
  • Binary Search template with [low, high) vs [low, high]
  • Handling worst-case linear degradation in duplicate search spaces

What You'll Learn

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

  • Understand why duplicates break the strict O(log N) guarantee in rotated binary search.
  • Master the safe boundary reduction technique: high-- when nums[mid] == nums[high].
  • Contrast comparing with nums[high] vs comparing with nums[low].

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:

  • Compare nums[mid] with nums[high].
  • nums[mid] > nums[high] -> low = mid + 1.
  • nums[mid] < nums[high] -> high = mid.
  • nums[mid] == nums[high] -> high-- (safely prune duplicate boundary).

Connected Patterns:

Find Minimum in Rotated Sorted Array (Unique Elements)Search in Rotated Sorted Array IIFind Peak Element

1. Linear Scan (Brute Force)

Intuition

Traverse the entire array and keep track of the minimum value.

Algorithm

  1. 1. Set minVal = nums[0].
  2. 2. For each element x in nums: - minVal = min(minVal, x).
  3. 3. Return minVal.

Brute Force Linear Scan Minimum Search

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 2, 2, 0, 1]
Current operationSTEP 1 OF 6
Phase 1 — minVal = 2 Begin linear scan: Step 1: Initialize minVal with the first element: minVal = 2
Visual state
Values and pointers at this exact step
array
S
2
2
2
0
1
0
↑ i=0 (val 2)
1
2
3
4
Variables at this step
i
0
val
2
minVal
2
Check / comparison
Initialize minVal = nums[0] = 2.
Decision / next transition
minVal = 2. Begin linear scan.
Why this step matters

Phase 1 — minVal = 2 Begin linear scan: Step 1: Initialize minVal with the first element: minVal = 2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// Brute Force Approach: Linear Scan
7int findMin(const vector<int>& nums) {
8 int minVal = nums[0];
9 for (int x : nums) {
10 minVal = min(minVal, x);
11 }
12 return minVal;
13}
14
15int main() {
16 vector<int> nums = {2, 2, 2, 0, 1};
17 int result = findMin(nums);
18 cout << "Output: " << result << endl;
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass visiting all N elements.
  • Space complexity: O(1) — Only constant extra variables are used.

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. Recursive Divide and Conquer (Better)

Intuition

Recursively explore search spaces when duplicates prevent directional narrowing.

Algorithm

  1. 1. Define helper solve(low, high).
  2. 2. If low == high, return nums[low].
  3. 3. mid = low + (high - low) / 2.
  4. 4. If nums[mid] > nums[high]: return solve(mid + 1, high).
  5. 5. If nums[mid] < nums[high]: return solve(low, mid).
  6. 6. Else: return solve(low, high - 1).

Divide & Conquer Two-Halves Minimum

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 2, 2, 0, 1]
Current operationSTEP 1 OF 6
Phase 1 — min(solve(0, 2), solve(3, 4)): Step 1: Split the array into two halves at mid = 2
Visual state
Values and pointers at this exact step
array
S
2
2
2
0
1
0
↑ L=0, R=4
1
2
↑ mid=2
3
4
Variables at this step
Range
[0..4]
mid
2
Left
[2, 2, 2]
Right
[0, 1]
Check / comparison
Divide range [0..4] at mid = 2: Left half [0..2] = [2, 2, 2], Right half [3..4] = [0, 1].
Decision / next transition
min(solve(0, 2), solve(3, 4)).
Why this step matters

Phase 1 — min(solve(0, 2), solve(3, 4)): Step 1: Split the array into two halves at mid = 2. Left half is [2, 2, 2], right half is [0, 1].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Better Approach: Recursive Divide and Conquer
6int solve(const vector<int>& nums, int low, int high) {
7 if (low == high) return nums[low];
8 int mid = low + (high - low) / 2;
9
10 if (nums[mid] > nums[high]) {
11 return solve(nums, mid + 1, high);
12 } else if (nums[mid] < nums[high]) {
13 return solve(nums, low, mid);
14 } else {
15 return solve(nums, low, high - 1);
16 }
17}
18
19int findMin(const vector<int>& nums) {
20 return solve(nums, 0, nums.size() - 1);
21}
22
23int main() {
24 vector<int> nums = {3, 3, 1, 3};
25 int result = findMin(nums);
26 cout << "Output: " << result << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(log N) avg, O(N) worst — Halves search space on average; in worst case of identical elements, shrinks by 1 each time.
  • Space complexity: O(log N) — Call stack consumes O(log N) on average, up to O(N) in worst case.

3. Iterative Binary Search with Duplicate Pruning (Optimal)

Intuition

Perform iterative binary search comparing mid to high, decrementing high when duplicates match.

Algorithm

  1. 1. Initialize low = 0, high = nums.length - 1.
  2. 2. While low < high: - mid = low + (high - low) / 2 - If nums[mid] > nums[high]: low = mid + 1 - Else if nums[mid] < nums[high]: high = mid - Else: high--.
  3. 3. Return nums[low].

Modified Binary Search with Duplicate Trimming

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 2, 2, 0, 1]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1 (Binary Search Step): nums[mid] = 2 > nums[R] = 1
Visual state
Values and pointers at this exact step
array
S
2
2
2
0
1
0
↑ L=0 (val 2)
1
2
↑ mid=2 (val 2)
3
4
↑ R=4 (val 1)
Variables at this step
L
0
R
4
mid
2
nums[mid]
2
nums[R]
1
Action
L = mid + 1 (3)
Check / comparison
L=0, R=4. mid = (0 + 4) / 2 = 2. nums[mid] = 2, nums[R] = 1. nums[mid] > nums[R] (2 > 1)!
Decision / next transition
Minimum MUST lie in right half (since sorted order broke). Set L = mid + 1 = 3.
Why this step matters

Phase 1 — Step 1: Step 1 (Binary Search Step): nums[mid] = 2 > nums[R] = 1. In a sorted rotated array, if mid > R, the rotation point (minimum) is strictly to the right! Advance L = mid + 1 = 3.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Optimal Approach: Iterative Binary Search with Duplicate Pruning
6int findMin(const vector<int>& nums) {
7 int low = 0, high = nums.size() - 1;
8
9 while (low < high) {
10 int mid = low + (high - low) / 2;
11
12 if (nums[mid] > nums[high]) {
13 low = mid + 1;
14 } else if (nums[mid] < nums[high]) {
15 high = mid;
16 } else {
17 high--;
18 }
19 }
20 return nums[low];
21}
22
23int main() {
24 vector<int> nums = {2, 2, 2, 0, 1};
25 int result = findMin(nums);
26 cout << "Output: " << result << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(log N) avg, O(N) worst — Halves search interval in O(log N) time when duplicates are distinct. In worst case (all identical elements), high is decremented N times: O(N).
  • Space complexity: O(1) — Uses only low, high, mid scalar pointers in O(1) space.

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)Scan through all elements and track the global minimum.Checks all elements unconditionally.
2.Better — Recursive Divide & ConquerO(log N) average, O(N) worstO(log N)Recurse on both halves when nums[mid] == nums[high].Function call frames.
3.Optimal — Modified Binary Search with Duplicate PruningOptimalO(log N) average, O(N) worstO(1)Binary search using high-- on equality.None; information-theoretic optimal bound.

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:

  • All elements identical: nums = [1, 1, 1, 1] -> high decrements to low and returns 1.
  • Array not rotated: nums = [1, 2, 3, 4] -> returns nums[0] = 1.
  • Single element array: nums = [5] -> loop terminates immediately and returns 5.

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 Find Minimum in Rotated Sorted Array II?

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

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

Back to DSA Sheet