LeetCode Q154: Find Minimum in Rotated Sorted Array II (hard)

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 a sorted array 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.

Solution:

The solution is basically the same to the question in which there is no duplicate element. Basically, for questions like this one which allows duplicate elements when doing binary search, we need to shrink the range by moving either left or right pointer when meeting duplicate element.

	class Solution {
	public:
	int findMin(vector<int>& nums) {
	int l=0;
	int r=nums.size()-1;
	while(l<r){
	int mid=(l+r)/2;
	if(l==mid||r==mid)
	return min(nums[l], nums[r]);
	if(nums[mid]>nums[r]){
	l=mid;
	continue;
	}
	if(nums[mid]<nums[l]){
	r=mid;
	continue;
	}
	if(nums[l]<nums[r])
	break;
	if(nums[l]==nums[r])
	r--;
	}
	return nums[l];
	}
	};

view raw Q154MinInRotatedSortedArray.cpp hosted with ❤ by GitHub

Round 2 solution: For all rotated array questions with duplicates, we can compare middle elements with left/right boundary, if identical, we can shrink the boundary.

	class Solution {
	public:
	int findMin(vector<int>& nums) {
	int res;
	if(nums.empty())
	return 0;
	int l = 0;
	int r = nums.size()-1;
	while(l<r-1){
	int mid = (l+r)/2;
	if(nums[mid]==nums[r]){
	r--;
	continue;
	}
	if(nums[mid]==nums[l]){
	l++;
	continue;
	}
	if(nums[l]<nums[mid])
	if(nums[mid]<nums[r])
	r=mid;
	else
	l=mid;
	else
	r=mid;
	}
	res = min(nums[l], nums[r]);
	return res;
	}
	};

view raw Q154Rnd2.cpp hosted with ❤ by GitHub