Log inSign up
mediumleetcodeNot Started

Find Minimum in Rotated Sorted Array

Given a sorted rotated array of unique elements, return the minimum element of this array in O(log n) time.

Binary Search
Solve on leetcode
Lesson

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:\n- [4,5,6,7,0,1,2] if it was rotated 4 times.\n- [0,1,2,4,5,6,7] if it was rotated 7 times.\n\nNotice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].\n\nGiven the sorted rotated array nums of unique elements, return the minimum element of this array.\n\nYou must write an algorithm that runs in O(log n) time.

Example 1 · Example 1: Rotated Array:

Input: nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: The original array was [1, 2, 3, 4, 5] rotated 3 times.

Example 2 · Example 2: Rotated 4 Times:

Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: The original array was [0, 1, 2, 4, 5, 6, 7] and it was rotated 4 times.

Example 3 · Example 3: Already Sorted:

Input: nums = [11, 13, 15, 17]
Output: 11
Explanation: The array is already sorted, so the minimum is 11.

Constraints:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All the integers of nums are unique.
  • nums is sorted and rotated between 1 and n times.

What You'll Learn

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

  • Understand why comparing with nums[high] correctly handles both rotated and non-rotated arrays.
  • Master the subtle high = mid boundary assignment vs high = mid - 1.
  • Achieve optimal O(log n) time complexity with constant space.

Pattern Recognition Trigger

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

Signals to Look For:

  • Array is sorted and rotated.
  • Need to find minimum / pivot element.
  • All elements are distinct.

Algorithmic Decision Tree:

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

Connected Patterns:

Find Minimum in Rotated Sorted Array II (with duplicates)Search in Rotated Sorted ArrayFind Peak Element

1. Linear Minimum Scan

Intuition

Initialize minVal = nums[0]. Iterate through all elements nums[i]. If nums[i] < minVal, update minVal. Return minVal at the end.

When to apply: Basic baseline when array properties are not utilized.

Algorithm

  1. Step 1: Initialize minVal with nums[0].
  2. Step 2: Loop from index 1 to n - 1.
  3. Step 3: Update minVal = min(minVal, nums[i]).
  4. Step 4: Return minVal.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int findMin(vector<int>& nums) {
10 int ans = nums[0];
11 for (int x : nums) ans = min(ans, x);
12 return ans;
13 }
14};
15
16int main() {
17 // Sample driver execution
18 cout << "Execution completed successfully." << endl;
19 return 0;
20}
21

Time & Space Complexity

  • Time complexity: O(n) — Must examine all n elements sequentially.
  • Space complexity: O(1) — Uses a single variable for minimum storage.

2. Linear Scan for Drop Point

Intuition

In a rotated sorted array, all adjacent pairs are ascending except at the pivot where nums[i] < nums[i-1]. Finding this drop point yields the minimum. If no drop is found, nums[0] is the minimum.

When to apply: When expecting the rotation point to occur very early in the array on average.

Algorithm

  1. Step 1: Iterate index i from 1 to n - 1.
  2. Step 2: If nums[i] < nums[i - 1], return nums[i].
  3. Step 3: If loop completes without drop, return nums[0].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int findMin(vector<int>& nums) {
10 for (int i = 1; i < (int)nums.size(); ++i) {
11 if (nums[i] < nums[i - 1]) return nums[i];
12 }
13 return nums[0];
14 }
15};
16
17int main() {
18 // Sample driver execution
19 cout << "Execution completed successfully." << endl;
20 return 0;
21}
22

Time & Space Complexity

  • Time complexity: O(n) — Worst case O(n) when minimum is at the last index or array is unrotated.
  • Space complexity: O(1) — Requires O(1) auxiliary memory.

3. Binary Search Comparing with Right Boundary

Intuition

Set low = 0 and high = n - 1. While low < high, calculate mid = low + (high - low) / 2. If nums[mid] > nums[high], the min lies strictly to the right of mid, so set low = mid + 1. Otherwise, nums[mid] <= nums[high], meaning min is at mid or to the left, so set high = mid. When low == high, return nums[low].

When to apply: Standard optimal solution required in technical interviews.

Algorithm

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

Trace for nums = [4, 5, 6, 7, 0, 1, 2]

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Initial state: low=0 (4), high=6 (2)
Visual state
Values and pointers at this exact step
pointers
S
4
5
6
7
0
1
2
0
↑ low
1
2
3
↑ mid
4
5
6
↑ high
Check / comparison
nums[mid]=7 > nums[high]=2 -> Minimum lies to the right of mid.
Decision / next transition
Set low = mid + 1 = 4.
Why this step matters

Initial state: low=0 (4), high=6 (2). mid=3 (7). Compare nums[mid]=7 with nums[high]=2. Since 7 > 2, the inflection point is in the right half. Discard left half including mid: low = mid + 1 = 4.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int findMin(vector<int>& nums) {
10 int low = 0, high = (int)nums.size() - 1;
11 while (low < high) {
12 int mid = low + (high - low) / 2;
13 if (nums[mid] > nums[high]) {
14 low = mid + 1;
15 } else {
16 high = mid;
17 }
18 }
19 return nums[low];
20 }
21};
22
23int main() {
24 // Sample driver execution
25 cout << "Execution completed successfully." << endl;
26 return 0;
27}
28

Time & Space Complexity

  • Time complexity: O(log n) — Search space is halved in each step, taking at most ceil(log2(n)) steps.
  • Space complexity: O(1) — Only constant extra variables are used.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Min ScanO(n)O(1)Check every element one by one.Inspects every single element.
2.Linear Drop ScanO(n)O(1)Scan for the first index where nums[i] < nums[i-1].Sequential traversal.
3.Binary Search (Comparing with High)OptimalO(log n)O(1)Halve search space by comparing nums[mid] with nums[high].None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single element: nums = [1] -> return 1.
  • Array not rotated (0 rotations or n rotations): nums = [1, 2, 3, 4] -> return 1.
  • Two element rotated: nums = [2, 1] -> return 1.
  • Rotated 1 time (max element at index 0): nums = [5, 1, 2, 3, 4] -> return 1.

Interview Tips & Best Practices

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

  1. Clarify why we compare with nums[high] instead of nums[0] (if unrotated, nums[mid] > nums[0] would incorrectly discard the left side containing the min).
  2. Highlight why high = mid retains the mid element (since mid could be the minimum itself).
  3. Show how the while loop condition low < high naturally converges to single index low == high.

Quick Comprehension Check

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

1.Why do we use high = mid instead of high = mid - 1 when nums[mid] <= nums[high]?

2.What happens if the array is not rotated at all (e.g., [1, 2, 3, 4, 5])?

Back to DSA Sheet