It seems we are having another nice spring day in the Twin Cities of Minneapolis and St. Paul. The sun is shining and the temperature is forecasted to reach the low 60s. On Saturday we are expecting high in the low 80s. That will be a record day. Will see when it arrives.
My wife and I are planning on grilling on Saturday and Sunday. For one reason and the other we have not enjoyed an “adult beverage” in a couple months. Grilling steaks while having a beer or two on a sunny and warm day is something worthwhile to do on a weekend. Will provide more info on Sunday if I am able to complete a problem and post it.
I decided to solve LeetCode 153 Find Minimum in Rotated Sorted Array. I just ran into this problem. Not sure if is in the list of problems I am currently solving from LeetCode.
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: [4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. 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. Constraints: o n == nums.length o 1 <= n <= 5000 o -5000 <= nums[i] <= 5000 o All the integers of nums are unique. o nums is sorted and rotated between 1 and n times.
The idea is to return the minimum element in the sorted array.
If interested please look at the current description of the problem in the LeetCode website. It seems that some problems may change with time.
class Solution {
public int findMin(int[] nums) {
}
}
The signature for the method in question is quite simple. We are provided an int[] array and we need to return the minimum value.
I will solve the problem using the Java programming language and the VSCode IDE on a Windows 10 machine. That said, it is simpler to solve the problem directly on the LeetCode web site because they provide a test scaffold and a large set of test cases. I will solve the problem on my computer. For this reason I will also need to generate my own test code. Please note that the test code IS NOT PART OF THE SOLUTION.
3,4,5,6,1,2 main <<< nums: [3, 4, 5, 6, 1, 2] main <<< output: 1 main <<< output: 1 3,4,5,1,2 main <<< nums: [3, 4, 5, 1, 2] main <<< output: 1 main <<< output: 1 4,5,6,7,0,1,2 main <<< nums: [4, 5, 6, 7, 0, 1, 2] main <<< output: 0 main <<< output: 0 11,13,15,17 main <<< nums: [11, 13, 15, 17] main <<< output: 11 main <<< output: 11 7 main <<< nums: [7] main <<< output: 7 main <<< output: 7 2,1 main <<< nums: [2, 1] main <<< output: 1 main <<< output: 1
We are provide a line with the values of the int[] which has already been rotated. Our test code seems to read the input line and generate and int[] array with the specified values.
Our test scaffolding seems to call two different implementations. The results seem to match in all cases. That is good but the final word is provided by LeetCode when they accept your submission. Both submissions were accepted as we will see shortly.
The test cases provide some insights on how to proceed. Let’s take a look at the first example. It appears that the array was rotated four times to the right. We need to return 1 as the result. After a quick inspection, it seems that the number we are looking follows the largest number in the array. We will talk more about this observation as we implement both versions of our solution.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
// **** read and create input array ****
int[] nums = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
// **** find and display min ****
System.out.println("main <<< output: " + findMin0(nums));
// **** find and display min ****
System.out.println("main <<< output: " + findMin(nums));
}
Our test code uses a buffer reader to read the input line. We then create and populate an array with the provided values. For sanity we display the populated array. We then call and display the resulting value on our two implementations.
/**
* Given the sorted rotated array nums of unique elements,
* return the minimum element of this array.
* Implements brute force approach.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.2 MB, less than 78.96% of Java online submissions.
*/
static int findMin0(int[] nums) {
// **** sanity check ****
if (nums.length == 1)
return nums[0];
// **** check if there is no rotation ****
if (nums[nums.length - 1] > nums[0])
return nums[0];
// **** loop looking for the next smallest value ****
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1])
return nums[i + 1];
}
// **** min not found ****
return -1;
}
Our first pass is simple (brute force). We check if there is only a single element.
We then check if the array was not rotated or of the rotations was a multiple of the array length.
We then set our min value to be the first entry in the array.
We enter a loop in which we look for an entry in which the next entry is smaller than the current one. This is the observation we came up with after looking at an input array. Such approach is correct but if we deal with a large array and the smallest value is toward the end, we will be very close to O(n) execution order. Not bad but we can probably do better.
/**
* Given the sorted rotated array nums of unique elements,
* return the minimum element of this array.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.2 MB, less than 64.79% of Java online submissions.
*/
static int findMin(int[] nums) {
// **** sanity check(s) ****
if (nums.length == 1)
return nums[0];
// **** initialization ****
int left = 0;
int right = nums.length - 1;
// **** check if there is no rotation ****
if (nums[right] > nums[left])
return nums[left];
// **** binary search approach ****
while (left < right) {
// **** compute mid point ****
int mid = left + (right - left) / 2;
// **** check if we found min ****
if (nums[mid] > nums[mid + 1])
return nums[mid + 1];
if (nums[mid - 1] > nums[mid])
return nums[mid];
// **** decide which way to go ****
if (nums[mid] > nums[0])
left = mid + 1; // go right
else
right = mid - 1; // go left
}
// **** min not found ****
return -1;
}
This is our second implementation. The problem appears to call for a binary search. In this case we will not be looking for a specified value but for the point in which the next element is smaller than the one in the left. This is exactly the same condition we used in our first approach.
Our code checks if the array contains a single entry. If so we are done.
Next we check if the array has not been rotated or has been rotated a multiple of n times. This would get back to the initial array.
Note that we initialize a couple variables between our checks. We could have moved the initialization after the second sanity check.
At this point we are ready to implement a binary search. The search is implemented with a while loop. We could have used a separate recursive method, but in-line code seems to perform faster because it does not make use of the stack.
We have previously implemented a binary search it at least this post in this blog. In the mentioned post we used recursion and two methods to achieve the same result as we are about to do in this post.
We compute the midpoint of the current array segment.
The following two checks are used to implement the same condition as we did in our previous method in this post. The second condition is used to address where mid falls. We need to take into account if the check skips the first condition. Please remove the second check and try the test cases. It will become clear.
Now we are done and have to split the current array span by choosing a new left or right boundary. Check the resemblance with the standard binary search when we are looking for a value in an array.
Finally, if we do not find the minimum we return a -1. The code should not hit this point but the compiler complains if our int method does not return a value. Note that a binary search executes in O(log(n)) which is faster than O(n).
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John