Find Minimum in Rotated Sorted Array II
Hard
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:
[4,5,6,7,0,1,4]if it was rotated4times.[0,1,4,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 that may contain duplicates, return the minimum element of this array.
You must decrease the overall operation steps as much as possible.
For example:
nums = [1, 3, 5] should return 1.
nums = [2, 2, 2, 0, 1] should return 0.
What is the most efficient way to solve this problem, what is the Big O run-time, what is the Big O space usage, and what are the edge cases?
Solution
Brute Force Solution
The simplest approach is to iterate through the array and find the minimum element. This involves comparing each element with the current minimum and updating the minimum if a smaller element is found.
def find_min_brute_force(nums):
min_val = nums[0]
for i in range(1, len(nums)):
min_val = min(min_val, nums[i])
return min_val
Time Complexity: O(n), as we iterate through each element of the array once.
Space Complexity: O(1), as we use only a constant amount of extra space.
Optimal Solution: Binary Search
Since the array is sorted and rotated, we can use binary search to find the minimum element more efficiently. The key idea is to compare the middle element with the left and right boundaries to determine which half of the array contains the minimum element.
However, the presence of duplicates complicates the algorithm. When nums[mid] == nums[left], we cannot determine which side the minimum element lies on, so we simply shrink the search space by incrementing left. Similarly, when nums[mid] == nums[right], we decrement right.
def find_min(nums):
left = 0
right = len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
elif nums[mid] < nums[right]:
right = mid
else:
right -= 1
return nums[left]
Edge Cases:
- Empty Array: The problem states that
1 <= n <= 5000, so the array will not be empty. - Single Element Array: The algorithm will correctly return the single element.
- Array with all same elements: The algorithm handles this case correctly by shrinking the search space.
- Already Sorted Array: The algorithm will correctly identify the first element as the minimum.
Time Complexity:
- In the best case (no duplicates and a clear rotation point), the time complexity is O(log n).
- In the worst case (all elements are the same), the time complexity degrades to O(n) because the
leftorrightpointer is incremented/decremented one at a time.
Space Complexity:
O(1), as we use only a constant amount of extra space.
