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.
This approach utilizes binary search to identify the smallest element in a rotated sorted array. The idea is based on the characteristics of the rotated array where at least one half of the array is always sorted. By comparing middle and right elements, we can decide whether the rotation point lies to the left or right of the middle element, effectively narrowing down the search space.
This C code implements a binary search algorithm to find the minimum element in a rotated sorted array. The function findMin utilizes two pointers, low and high, to define the current search space. It updates low when the middle element is greater than the element at high, indicating the rotation point is in the upper half. Otherwise, it contracts high, thereby searching in the lower half.
Time Complexity: O(log n) where n is the number of elements in the input array.
Space Complexity: O(1) as no extra space is used except for variables.
This approach involves linearly iterating through the array to find the minimum value. While it doesn't meet the time complexity requirement of O(log n), it serves as a straightforward method to understand the array's properties and validate the binary search approach.
This C solution performs a simple iteration through the array to check each element against a minimum variable, thus directly finding the smallest number. This method ensures you check every element, although not achieving the optimal logarithmic time.
Time Complexity: O(n), as it requires traversal of the entire array in the worst-case scenario.
Space Complexity: O(1), with no additional space usage outside the input list.
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time Complexity: O(log n) where n is the number of elements in the input array. |
| Iterative Approach | Time Complexity: O(n), as it requires traversal of the entire array in the worst-case scenario. |
| 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 |
Find Minimum in Rotated Sorted Array - Binary Search - Leetcode 153 - Python • NeetCode • 455,076 views views
Watch 9 more video solutions →Practice Find Minimum in Rotated Sorted Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor