[LeetCode] 154. Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
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.

Thought process:
This would affect the time complexity. For example, the array could contain a bunch of 1s and one 0. If we do a binary search on it, we could have left = mid = right = 1. We don't know in which direction the 0 is. So in the worst case, the time complexity is O(n). But we can still use binary search to improve the average case run-time.
The idea is to eliminate the edge case where left = mid = right at the beginning of each loop. After that, if we compare nums[mid] with the last element in the array, there are two cases:
  1. nums[mid] <= last element: the minimum element is to the left of mid.
  2. nums[mid] > last element: the minimum element is to the right of mid.

Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int last = nums[right];
        
        while (left + 1 < right) {
            if (nums[left] == nums[right]) {
                left++;
                continue;
            }
            
            int mid = left + (right - left) / 2;
            if (nums[mid] <= last) {
                right = mid;
            } else {
                left = mid;
            }
        }
        
        if (nums[left] < nums[right]) {
            return nums[left];
        } else {
            return nums[right];
        }
    }
}

Time complexity: 
O(logn) in the average case. O(n) in the worst case.

Comments

Popular posts from this blog

[LeetCode] 714. Best Time to Buy and Sell Stock with Transaction Fee

[LeetCode] 269. Alien Dictionary

[LeetCode] 631. Design Excel Sum Formula