23 Oct 2023, 3:07 PM
23 Oct 2023, 3:07 PM

17. Find Minimum in Rotated Sorted Array

#leetcode/153

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

Example:

Input: nums = [3,4,5,1,2]
Output: 1

Solution

Solution in C++ using recursion

The approach is reminiscent of binary search, where the search range is continually narrowed down based on certain conditions. However, we have to do some changes. There are three main cases to consider:

  1. If nums[i] <= nums[j] or if i <= j, it means that the subarray is already sorted, and nums[i] is the minimum element. This serves as the base case for the recursion.
  2. If nums[m] > nums[j], it means that the minimum value must have occurred somewhere to the right of m (you can see it with some examples). Therefore, the search is continued in the right subarray, and findMinRec is called recursively with the new range from m + 1 to j.
  3. If nums[m] <= nums[j], it means that the pivot or the minimum value must be at index m or to the left of m. The search is continued in the left subarray, but without discarding m as it still might have the minimum value.

Here's the implementation.

int findMin(vector<int>& nums) {
	return findMinRec(nums, 0, nums.size() - 1);
}
int findMinRec(vector<int>& nums, int i, int j) {
	int m = (i + j) / 2;
	/*
		if nums[i] < nums[j] we can stop because nums[i] will have the minimum
		value
	OR
		if i >= j we can stop because we have one element
	*/
	if(nums[i] < nums[j] || i >= j)
		return nums[i];
	
	/*
		if nums[mid] > nums[j], we KNOW that the pivot/minimum value must 
		have occurred somewhere to the right of mid, which is why the values 
		wrapped around and became smaller.
        
        example:  [3,4,5,6,7,8,9,1,2] 
        in the first iteration, when we start with mid index = 4,
        right index = 9.
        
		In addition, we know that the number at mid is greater than at least
	    one number to the right, so we can use mid + 1 and never consider mid 
	    again
	*/
	else if(nums[m] > nums[j])
		return findMinRec(nums, m + 1, j);

	/* 
		here, nums[m] <= nums[j], then we KNOW the pivot must be at mid or to 
		the left of mid:
	
		example: [8,9,1,2,3,4,5,6,7]
        in the first iteration, when we start with mid index = 4,
        right index = 9.
		if nums[mid] <= nums[right], we know the numbers continued increasing 
		to the right of mid, so they never reached the pivot and wrapped 
		around. Therefore, we know the pivot must be at index <= mid.
		
		Then, we explore the left part of the array, but without discarding 
		the mid value! It still might have the minimum value.
	*/
	else
		return findMinRec(nums, i, m);
}

Solution in C++ without recursion

For the sake of completeness, here's the iterative implementation.

int findMin(vector<int>& nums) {
	int i = 0, j = nums.size() - 1;

	while(i < j && nums[i] > nums[j]) {
		int m = (i + j) / 2;
		if(nums[m] > nums[j])
			i = m + 1;
		else
			j = m;
	}
	return nums[i];
}