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

[@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]; }

[@barkaleamol9394]

OMG!!!!!!!!!!!!!! Bro, you are too brilliant, I spent a full day and tried with so many types. how you did it. I am a new coder but I loved your approach man thankssssss!

[@西雅图UrbanEdge整屋家具]

It is great. But Nick's solution has slightly better time complexity.

[@iRockTheBeat1]

The problem requires you to solve it in O(log n) time not O(n) time.

[@iRockTheBeat1]

@likhith chinnam My bad, I thought he wasn't using binary search. This solution is still O(logn).

[@enigma8549]

you are og

[@mohitmotwani9256]

Nice work!! More staright forward code (c++) class Solution { public: int findMin(vector& 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]; } };

[@anuradhapandey2173]

Can you please explain why you returned nums[high]??

[@mohitmotwani9256]

@@anuradhapandey2173 because if you see in the else part, we assign high as mid. Also, if you dry run this algo you will get to know why high.

[@kaanatacan1759]

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!

[@MichaelSalo]

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

[@eugbyte1822]

anyone can explain?

[@mdsaifhussainiqbal2236]

@@eugbyte1822 the whole point is to make l=r because when l=r then while loop break and the single element left and that is your minimum number

[@xav8812]

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.

[@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]

[@kshitizsharma2923]

ig its for the case where midpoint can be same as the left index .

[@blazer511]

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

[@NickWhite]

Aaron Brown hell yeah man make sure to throw me a like so the algorithm promotes me

[@blazer511]

@@NickWhite I did haha! I made sure to before the video ended. I noticed that there were zero likes and it would be wrong for me to comment and not hit that thumbs up

[@NickWhite]

You’re a good man

[@f3-faithfitnessfinance]

@@NickWhite and you are a great man

[@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(lowarr[high]){ low=mid+1 } else{ high=mid } } return arr[low] };

[@bhavyasharma4863]

but if the array is not rotated at all then we will need the conditions

[@poorpanda9033]

@@bhavyasharma4863 yes makes sense !

[@irinasaghoian5920]

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

[@jaitehkaba8753]

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

[@saldanaswiz1291]

how'd it go

[@jaitehkaba8753]

@@saldanaswiz1291 I just finished my internship at Microsoft today and got a return offer. I still come to this site just for fun.

[@transam351]

@@jaitehkaba8753 What TC did they offer you?

[@rupalitiwari5012]

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

[@cwagnello]

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

[@dp4kallday]

As you keep dividing the array in half, you eventually get an array with a single element which would be nums[0] and left is originally set to that value.

[@prakanshmishra9004]

@@dp4kallday Just wanted to point that what you stated is wrong. The array after getting divided by two and becoming smaller doesn't end at nums[0], but actually at any nums[i], where 0

[@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

[@doruwyl]

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

[@zishanshaikh3068]

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

[@ALEEMKHAWAR1]

pretty good explanation nick !!!

[@putinscat1208]

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?

[@GauravSingh-ku5xy]

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& nums) { int n = nums.size(), left, right, mid; if(nums.size()==1){ return nums[0]; } if(nums[0]

[@gtacarlito]

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

[@KNukzzz]

No it does not

[@ALifeExp]

This is a not a pivoted array, it's just a descending ordered array so it's not in the scope of this exercise ;)

[@ayansrivastava731]

def binary(A,st,en): while(True): mid=(st+en)//2 if(A[mid]

[@shaanyahoo]

last 10 seconds was the best :)

[@Nishant-qw7jk]

Hey that's a great explanation

[@jasonahn8658]

Getting index -1 out of bounds for length 2

[@shivanshupandey3637]

very good explanation

[@tanson86]

Why don't you just identify the pivot and return the number at the pivot. Finding pivot is just like how you did it for leetcode 33.

[@bayareamountainbiker]

Why can't it be just Arrays.sort(nums); return nums[0]?

[@xav8812]

it will be in O(nlogn), question asked to do in O(logn)

[@raj_kundalia]

thank you!

[@transam351]

You need sleep man

[@SayanKarmakar12]

Believe me, it was a very good explanation!

[@emmanuelmiramonvazquez9591]

9:35 same thought here 😂

[@bhavyasharma4863]

hey good explanation by the way you look like shown murfy from the good doctor

[@usa5450]

Best explanation of this problem No BS and so crisp 👍🏻

[@rishikeshpuri740]

thnx bro for this

[@kaaviyabaskaran1041]

Hi, first of all thanks for this video, it really made me understand the concept well. However, when I executed this on Leetcode, I am getting an error that the time limit exceeded. Could you explain why?

[@siddharth_chatterjee]

hmm, nice one

[@justiceessiel6123]

so who as the thought of just doing min(nums) that was my brute force😂.. its more efficient than this

[@sarveshzeke7255]

not successfull in leetcode now . idk why !

[@deepakanuraagsathyanarayan9666]

i feel binary search is too hard to simulate and write the edge cases did u see that he returned nums[left] why? i am figuring it out right now

[@rudyyyxu]

left and right becomes the same thing, which is the last element left

[@parthkumar1033]

If the array is not rotated simply then nums[left] should be min.

[@ayushsharma8950]

Hey can't I use arrays.sort in it and print the element at 0 index???

[@dossymzhankudaibergenov8193]

It’s time complexity is O(nlogn), this problem requires O(logn)

[@mujtabahussain7015]

if it weren't for O(log(N)), then ideal solution should have been linear search, sorting and then searching is very slow and inefficient.

[@SandyRocks007]

Why not use HashSet ? I am new to programming import java.util.*; class Solution { public int findMin(int[] nums) { HashSet h = new HashSet(); for(int x : nums){ h.add(x); } System.out.println(h); return (Integer)Collections.min(h); } }

[@NoWarForever]

Try to analyze space and time of your algorithm and you will know the reason :)

[@bhavuks6554]

HashSet will have O(N) worst case time complexity {where N = number of elements in the array} whereas Binary search will do it in O(LogN). Hope that helps.