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 an unknown pivot. The order is still increasing within each segment, but the smallest element marks the rotation point. Your task is to return that minimum element in the array.
Approach 1: Iterative Linear Scan (O(n) time, O(1) space)
The simplest strategy is to iterate through the array and track the smallest value seen so far. Start with the first element as the current minimum and update it whenever a smaller value appears during traversal. Since a rotated array still contains all elements exactly once, the smallest value must appear somewhere during the scan.
This method uses a single pass with constant extra memory. It works regardless of rotation position and does not rely on the array being partially sorted. However, it ignores the structure of the rotated sorted array and therefore runs in O(n) time with O(1) space.
Approach 2: Binary Search on Rotation Point (O(log n) time, O(1) space)
The optimal solution uses Binary Search. In a rotated sorted array, at least one half of the array remains sorted. Compare the middle element with the rightmost element to determine which side contains the minimum. If nums[mid] > nums[right], the minimum lies in the right half because the rotation pivot is there. Otherwise, the minimum is in the left half including mid.
Repeatedly shrink the search space using two pointers left and right. Each step eliminates half of the remaining elements, similar to classic binary search on a sorted array. The loop stops when left == right, which directly points to the minimum value.
This works because the rotation creates exactly one discontinuity where the order resets. Binary search efficiently locates this pivot without scanning every element. The algorithm runs in O(log n) time and uses O(1) space.
The approach combines properties of sorted arrays and rotation behavior, making it a classic example of applying array analysis with binary search techniques.
Recommended for interviews: Interviewers expect the binary search solution. A linear scan shows you understand the problem, but it does not leverage the rotated sorted property. The O(log n) binary search demonstrates algorithmic reasoning and the ability to adapt classic search patterns to modified array structures.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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 approach when constraints are small or rotation properties are ignored |
| Binary Search on Rotation Pivot | O(log n) | O(1) | Optimal solution when the array is sorted then rotated and you need logarithmic performance |
Search in rotated sorted array - Leetcode 33 - Python • NeetCode • 413,348 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