Watch 10 video solutions for Find Minimum in Rotated Sorted Array, a medium level problem involving Array, Binary Search. This walkthrough by NeetCode has 413,348 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
[4,5,6,7,0,1,2] if it was rotated 4 times.[0,1,2,4,5,6,7] if it was rotated 7 times.Notice 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]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
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:
Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
Constraints:
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums are unique.nums is sorted and rotated between 1 and n times.Problem Overview: You receive a sorted array that has been rotated at some unknown pivot. The order is still increasing, but the smallest element is no longer guaranteed to be at index 0. The task is to find the minimum element efficiently without fully sorting or scanning the array unnecessarily.
Approach 1: Iterative Linear Scan (O(n) time, O(1) space)
The most direct approach is to iterate through the array and track the smallest value seen so far. Start with min = nums[0] and update it while traversing each element. Because the array is only partially rotated, this method still works correctly for every case. The downside is performance: you examine every element even though the array retains sorted structure that could be exploited.
A small optimization is checking where the order breaks. During iteration, if nums[i] < nums[i-1], that element is the minimum because rotation creates exactly one drop point. Even with this improvement, worst‑case time complexity remains O(n) with constant O(1) space.
Approach 2: Binary Search (O(log n) time, O(1) space)
The optimal strategy uses binary search. Even though the array is rotated, it still contains two sorted segments. Compare the middle element with the right boundary to determine which half contains the minimum.
If nums[mid] > nums[right], the minimum must be in the right half because the rotation pivot lies there. Move the left pointer to mid + 1. Otherwise, the minimum is in the left half (including mid), so move the right pointer to mid. Continue shrinking the search window until left == right. That index holds the smallest value.
This works because one side of the array is always strictly sorted. The comparison with the right boundary tells you whether the pivot lies to the left or right of mid. Each iteration halves the search space, giving a time complexity of O(log n) with constant O(1) space.
The problem primarily involves arrays and modified binary search. Recognizing that rotation preserves partial ordering is the key insight that allows logarithmic search.
Recommended for interviews: Interviewers expect the binary search solution. A linear scan shows you understand the problem and guarantees correctness, but it ignores the sorted property. The binary search approach demonstrates stronger algorithmic thinking by leveraging the rotated sorted structure to reach O(log n) time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Linear Scan | O(n) | O(1) | Simple baseline solution or when binary search conditions are not guaranteed |
| Binary Search | O(log n) | O(1) | Best choice when the array is rotated but originally sorted |