LeetCode 153. Find Minimum in Rotated Sorted Array (Algorithm Explained)

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[mehroosali]

More simpler code -
public static int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;

if(nums[mid] < nums[right]) {
right = mid;
} else {
left = mid+1;
}
}
return nums[left];
}

[kaanatacan]

The explanation was pretty good, just don't worry and keep going to make videos. Normally, I don't write comments but thank you man, really!

[blazer]

Hi Nick, I liked this one, it's clean and 100 percent faster

[sgrpnwr]

There are too many unnecessary conditions here... It is understood that if the left part of the array is sorted, that will mean that right part of the array is unsorted and vice versa. And rather than checking the adjacent variable, we can just keep moving the left index towards unsorted array and return the low at the end.

Check the code below:

var findMin = function(arr) {

let low=0;
let high=arr.length-1;

while(low<high){
let mid=Math.floor((low+high)/2);
if(arr[mid]>arr[high]){
low=mid+1
}
else{
high=mid
}
}
return arr[low]
};

[AndrewCJXing]

Hey Nick thanks for the vid. The logic of binary search is pretty straightforward but it is the small details that sometimes throw things off, like why nums[left] <= nums[midpoint] but not nums[left] < nums[midpoint]. It'd be great if you could also cover that in your video.

[mohitmotwani]

Nice work!!
More staright forward code (c++)
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
if(n == 0) return -1;
int mid;
int low = 0;
int high = n -1 ;
while(low < high)
{
mid = low + (high - low)/2;
if(nums[mid] > nums[high])
low = mid+1;
else
high = mid;
}
return nums[high];
}
};

[MichaelSalo]

The loop condition (left < right) isn’t explained as different than a regular binary search.

[xav]

This is how we need to really think about when solving the question on leetcode by specific solution on specific questions, not just using the general solving method to submit all of similar questions.

[irinasaghoian]

Thank you for keeping it short in the intro we appreciate it!

[jaitehkaba]

Nick, you are a star!!! I have my interview with Microsoft next week. Pray for me.

[zishanshaikh]

Hey Nick, Great explanation, Thank you for making these videos, they are really helpful, please keep making more videos.

[doruwyl]

Hi Nick!
Probably got unnoticed, but your LinkedIn URL is incomplete. (from video description)

[ZhouHaibo]

A simper version.

public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right-left) / 2;
if (nums[mid] < nums[right]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];
}

[dev-skills]

No need for line 3 to check `if (nums.length == 0) return -1` as the problem specifies 1 <= n <= 5000

[rupalitiwari]

Code doesn't work for input [3, 3, 1, 3]

[cwagnello]

How do you know the value will be at index "left"?

[putinscat]

Personally, if I got down to 2 or 3 elements in an array, I would just find the min in that array. This would solve having some complex code to determine the middle on a 2 element array. A couple of important assumptions with this question, 0 is the lowest int allowed, and the original array is sorted low to high before rotation. I would love to know what the point of this is in real life?

[ayansrivastava]

def binary(A, st, en):

while(True):

mid=(st+en)//2
if(A[mid]<A[mid-1] ):
return A[mid]
elif(A[mid]<A[st]):
en=mid
elif(A[mid]>A[st]):
st=mid
this code is showing time limit exceeded. any idea why??

[GauravSingh-kuxy]

Need a little help. I have a similar solution based on binary search. Until the commented line (Main program starts here), I have taken care of all the edge cases. After that, it's just a normal binary search program modified for this problem. But in the test case [3, 4, 5, 1, 2] it says that the function does not return any value. But if I dry run it, it does. What am I doing wrong?

int findMin(vector<int>& nums) {
int n = nums.size(), left, right, mid;

if(nums.size()==1){
return nums[0];
}
if(nums[0]<nums[1] && nums[0]<nums[n-1]){
return nums[0];
}
if(nums[n-1]<nums[n-2] && nums[n-1]<nums[0]){
return nums[n-1];
}
left = 0; // Main program starts here.
right = n-1;
while(left<right){
mid = left + (right-left)/2;
if(nums[mid]<nums[mid-1]){
return nums[mid];
}
else if(nums[left]<nums[mid]){
left = mid+1;
}
else{
right = mid-1;
}
}
}

[gtacarlito]

Thanks for the algo, but does it work when our input is [2, 1] ???