154. Find Minimum in Rotated Sorted Array II
Explanation
To find the minimum element in a rotated sorted array that may contain duplicates, we can apply a modified binary search algorithm. The idea is to compare the middle element with the rightmost element to determine which half of the array to discard. If the middle element is greater than the rightmost element, we know the minimum element must be in the right half. If they are equal, we can move the right pointer one step to the left and continue the search. By iteratively narrowing down the search range, we can find the minimum element efficiently.
The time complexity of this algorithm is O(log n) where n is the number of elements in the array. The space complexity is O(1) since we are not using any additional data structures.
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right && nums[left] >= nums[right]) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
right--;
}
}
return nums[left];
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.