154-find-minimum-in-rotated-sorted-array-ii

Question

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input: [1,3,5],
Output: 1

Example 2:

Input: [2,2,2,0,1],
Output: 0

Note:

• This is a follow up for "Find Minimum in Rotated Sorted Array".
• Would allow duplicates affect the run-time complexity? How and why?

Thought Process

1. Two Pointers
   1. Similar to previous question, we need to find where to find our minium
   2. We compare mid element to the end element
      1. When nums[mi] < nums[hi], it's on the left, so we set hi = mi
      2. When nums[mi] > nums[hi], is's on the right because the pivot point has to be on the right
      3. Lastly, when nums[mi] == nums[hi], we decrease the hi and keep finding
   3. Time complexity O(n)
   4. Space complexity O(1)

Solution

class Solution {
    public int findMin(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (nums[mi] < nums[hi]) hi = mi;
            else if (nums[mi] > nums[hi]) lo = mi + 1;
            else hi--;
        }
        return nums[lo];
    }
}

Additional