Find Minimum in Rotated Sorted Array
MedPrompt
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 rotated4times.[0,1,2,4,5,6,7]if it was rotated7times.
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] <= 5000- All the integers of
numsare unique. numsis sorted and rotated between1andntimes.
Approaches
2 approaches with complexity analysis and trade-offs.
This is a straightforward brute-force approach. We can find the minimum element by simply iterating through the entire array and keeping track of the smallest value encountered.
Algorithm
- Initialize a variable
min_elementto the first element of the array,nums[0]. - Iterate through the array from the second element (
i = 1) to the end. - In each iteration, compare the current element
nums[i]withmin_element. - If
nums[i]is smaller, updatemin_elementtonums[i]. - After the loop finishes,
min_elementwill hold the smallest value in the array.
Walkthrough
The algorithm initializes a variable, say min_element, with the value of the first element in the array. It then iterates through the rest of the array from the second element to the last. In each iteration, it compares the current element with min_element. If the current element is smaller than min_element, min_element is updated to the value of the current element. After the loop completes, min_element will hold the minimum value in the array. This approach is simple but overlooks the sorted and rotated nature of the array, leading to a suboptimal time complexity.
class Solution { public int findMin(int[] nums) { if (nums == null || nums.length == 0) { // This case is ruled out by constraints but good practice. throw new IllegalArgumentException("Input array is empty or null."); } int minElement = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i] < minElement) { minElement = nums[i]; } } return minElement; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Very simple to understand and implement.
It is guaranteed to find the minimum element for any array of numbers, not just rotated sorted ones.
Cons
This approach is inefficient and does not meet the O(log n) time complexity requirement specified in the problem description.
It fails to utilize the key property of the input, which is that the array is a rotated version of a sorted array.
Solutions
Solution
class Solution { public int findMin ( int [] nums ) { int n = nums . length ; if ( nums [ 0 ] <= nums [ n - 1 ]) { return nums [ 0 ]; } int left = 0 , right = n - 1 ; while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( nums [ 0 ] <= nums [ mid ]) { left = mid + 1 ; } else { right = mid ; } } return nums [ left ]; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.