Find Minimum in Rotated Sorted Array II (Duplicates)

Share

Same as Find Minimum in Rotated Sorted Array but the array may contain duplicates. Return the minimum element.

Example 1
Input: [1,3,5] → Output: 1
Example 2
Input: [2,2,2,0,1] → Output: 0

Solution Approach

Similar to version I but when nums[mid] == nums[hi] we cannot determine which half contains the minimum, so we decrement hi by 1.

  • While lo < hi:
  • If nums[mid] > nums[hi]: lo = mid + 1.
  • Else if nums[mid] < nums[hi]: hi = mid.
  • Else (nums[mid] == nums[hi]): hi-- (safely shrink).
Java
class Solution {
    public int findMin(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[hi]) lo = mid + 1;
            else if (nums[mid] < nums[hi]) hi = mid;
            else hi--;
        }
        return nums[lo];
    }
}
  • Time Complexity: O(N) worst case (all duplicates), O(log N) average
  • Space Complexity: O(1)