Thank you so much for building up the intution, I am going to buy lifetime Neetcode subscription, once I crack a job. You are the best instructor and teacher.💝💝
if you calculate mid as int mid = left + (right - left) / 2, it's already a left biased mid (there an alternative approach to make mid right biased), in the case of left biased mid do (m + 1) instead of m - 1 to not worry about out of bounds on the left, left biased mid protects you from the out of bounds condition happening on the right
@@takerixgaming4170 Well, it's the same as Neet's, but there are three differences: 1. He uses: *mid = (l+r)//2* instead of: *mid = left + ((right - left) / 2)* because he doesn't have to check for the overflow, as Neet himself noted as well. He just showed us this as a general good thing to know about a Binary Search. 2. His first if statement is: *if (nums[mid] < nums[mid + 1])* instead of: *if (mid > 0 and nums[mid - 1])* because this way you don't have to check for "mid > 0" or "mid < len(nums) - 1". Why is this the case? Well, when calculating "mid" pointer at the beginning of the loop we're using an integer division. Meaning it's always "cut down". So we're sure that nums[mid + 1] will never be out of bounds. 3. He doesn't have an "else" statement that breaks the loop, i.e. that returns "mid", instead his while loop breaks once left becomes greater than or equals to the right. Thus, at the end, out of the while loop, just return "left", since we're sure that is the answer. Run a Simulation or two on this code and you'll get it. I hope this helps.
what if we are at a point and on both the sides we find numbers which are greater than the current number, then in that case, which side do we need to go with our Binary Search?
I don't get the explanation at 9:29 if m==0 then it IS greater than its left neighbour as according to problem description the outOfBound element is -inf
ua-cam.com/video/HtSuA80QTyo/v-deo.html MITx 6.006 if you want a deeper understanding on Peak Finding. Professor Devadas also talks about 2D Peak Finding.
I was thinking what if more than 1 peaks and how i could find all peaks with this solution. Then i read expl. It says any of the peaks. So we just need to get close to one peak and look for it index
I believe the problem cannot be solved in O(log n) time. For example, given the sequence [1, 2, 1, 2, 3, 4, 5, 7, 7], the correct answer should be 1. However, the solution with a time complexity of O(log n) would yield 7, which is incorrect.
I'm not sure I understand why there's always a peak. What would be the peak in the array [1, 2, 2, 1]? If the "peak" is directly next to an equal value, it's not strictly greater than it's neighbors, and if the values on the ends of the array aren't larger, is there actually a peak?
My solution to this problem actually by searching the maximal value of an array then return the index of that value. If using python we just need to call max and using index() method
For binary search to work, the input must be sorted, is it sorted? I don’t see that in the requirements/constraints. I don’t see about repeated elements either. Such a crappy problem description.
It is not sorted. And no, it doesn't have to be sorted unless you are searching for an element in an array. Binary search is more about taking the middle of array and ignoring other side. So in this problem when we take mid element and we see that right side is less but left side is greater we go to left. Peak might be in right side too but it is not guaranteed because it can monotonically decrease. How about left side ? Either this monotonically increases or it goes down and both case is acceptable so we just ignore the right side. Binary search is much more than finding element in sorted array.
you need a better font or stop using one letter variables. I've got a time limits because it turned into an infinite loop because i put 1 instead of L in the middle point equation
I mean that error is easy to spot if you understood his explanation. The point of the video isn't for the viewers to copy his code, its for them to understand the explanation.
@@DinujayaRajakaruna i used another language and wasted a bunch of minutes becaise of it. i understand that leetcode is not about good code, but fast one, but still why not to improve to the sane degree?
@@DeathSugar While I do agree making things more readable helps in general, I think someone that is familiar with binary search will immediately understand what things like "r" and "l" stand for. Especially after he mentions what they are in the video.
@@DinujayaRajakaruna problem not with understaning. It uses "magic" evaluation to prevent from violating boundries - thats where I messed up with the 1/l.
@@DeathSugar it's not "magic" though, m = l + floor((r-l)/2) is exactly how you calculate the midpoint of l and r without getting any overflow issues. The standard way is m = floor((l+r)/2) but if l and r are large enough this overflows. He mentions this in the video, and this fact is mentioned in the Wikipedia page for binary search as well.
RIP to all those who got this in an interview without solving it before
I think if the interviewer mention o logn, it will be very straightforward
peak comment
Thank you so much for building up the intution, I am going to buy lifetime Neetcode subscription, once I crack a job. You are the best instructor and teacher.💝💝
if you calculate mid as int mid = left + (right - left) / 2, it's already a left biased mid (there an alternative approach to make mid right biased), in the case of left biased mid do (m + 1) instead of m - 1 to not worry about out of bounds on the left, left biased mid protects you from the out of bounds condition happening on the right
we can simplify the code a little bit more
l,r=0,len(nums)-1
while l < r:
mid = (l+r)//2
if nums[mid]< nums[mid+1]:
l=mid+1
else:
r=mid
return r
I can't understood bro
@@takerixgaming4170 Well, it's the same as Neet's, but there are three differences:
1. He uses:
*mid = (l+r)//2*
instead of:
*mid = left + ((right - left) / 2)*
because he doesn't have to check for the overflow, as Neet himself noted as well. He just showed us this as a general good thing to know about a Binary Search.
2. His first if statement is:
*if (nums[mid] < nums[mid + 1])*
instead of:
*if (mid > 0 and nums[mid - 1])*
because this way you don't have to check for "mid > 0" or "mid < len(nums) - 1". Why is this the case? Well, when calculating "mid" pointer at the beginning of the loop we're using an integer division. Meaning it's always "cut down". So we're sure that nums[mid + 1] will never be out of bounds.
3. He doesn't have an "else" statement that breaks the loop, i.e. that returns "mid", instead his while loop breaks once left becomes greater than or equals to the right.
Thus, at the end, out of the while loop, just return "left", since we're sure that is the answer.
Run a Simulation or two on this code and you'll get it.
I hope this helps.
Go mid
If peak return
If right is greater drop left
If left is greater drop right
Repeat
what if both left and right element are grater than mid?
@@kryptoknight992 Go any way depending on which side your program is checking. Both side there is at least 1 peak
Great explanation, thanks
Awesome explanation
A greedy binary search if you will
what if we are at a point and on both the sides we find numbers which are greater than the current number, then in that case, which side do we need to go with our Binary Search?
thank you...built the intuition
I don't get the explanation at 9:29 if m==0 then it IS greater than its left neighbour as according to problem description the outOfBound element is -inf
You are literally the goat.
I don't know how you make it look pretty simple🙂
ua-cam.com/video/HtSuA80QTyo/v-deo.html
MITx 6.006 if you want a deeper understanding on Peak Finding. Professor Devadas also talks about 2D Peak Finding.
Great Explanation.
Whenever I solve this problem , "I am peaky blinder" is the song that comes into my mind
Perfect explanation
It won't work for when the list contains the same number throughout right? Coz this code will return m rather None.
Adjacent elements must be different
I was thinking what if more than 1 peaks and how i could find all peaks with this solution. Then i read expl. It says any of the peaks. So we just need to get close to one peak and look for it index
Thanks.
Inspiring👍
elegant 👍
What would happen if you had [3,2,3,3]. Then the peak element would be on the left but both are greater than the 2 so how would you know?
oh I didnt read one of the constraints never mind
So basically we just guessing on which side we gonna have the peak?
what if it s a valley element i.e 1 2 1 2 3 with mid at the middle 1. Then both sides are equally applicable for binary search?????
You only need to guarantee the side you're looking for has a peak. You can return any peak, not the global max.
U a Peak God
A simpler one:
def findPeakElement(nums: List[int]):
low, high = 0, len(nums)-1
while low < high:
mid = low + (high - low) //2
if arr[mid+1] > arr[mid]:
low = mid + 1
else:
high = mid
return low
I believe the problem cannot be solved in O(log n) time. For example, given the sequence [1, 2, 1, 2, 3, 4, 5, 7, 7], the correct answer should be 1. However, the solution with a time complexity of O(log n) would yield 7, which is incorrect.
no two neighbouring numbers are equal, check constraints
@Pratik-tk6ts thanks, did not see that constraint
I'm not sure I understand why there's always a peak. What would be the peak in the array [1, 2, 2, 1]? If the "peak" is directly next to an equal value, it's not strictly greater than it's neighbors, and if the values on the ends of the array aren't larger, is there actually a peak?
read the constraints
numbers adjacent to each other can't be equal
If you're looking for todays daily LC (design browser history) 👉ua-cam.com/video/i1G-kKnBu8k/v-deo.html
My solution to this problem actually by searching the maximal value of an array then return the index of that value. If using python we just need to call max and using index() method
The question states that an O(log n) solution is required. Searching for the max element is a linear O(n) solution.
For binary search to work, the input must be sorted, is it sorted?
I don’t see that in the requirements/constraints.
I don’t see about repeated elements either.
Such a crappy problem description.
It is not sorted. And no, it doesn't have to be sorted unless you are searching for an element in an array. Binary search is more about taking the middle of array and ignoring other side. So in this problem when we take mid element and we see that right side is less but left side is greater we go to left. Peak might be in right side too but it is not guaranteed because it can monotonically decrease. How about left side ? Either this monotonically increases or it goes down and both case is acceptable so we just ignore the right side. Binary search is much more than finding element in sorted array.
@@shamilgurban6439 Legend !! Thanks man
you need a better font or stop using one letter variables. I've got a time limits because it turned into an infinite loop because i put 1 instead of L in the middle point equation
I mean that error is easy to spot if you understood his explanation. The point of the video isn't for the viewers to copy his code, its for them to understand the explanation.
@@DinujayaRajakaruna i used another language and wasted a bunch of minutes becaise of it. i understand that leetcode is not about good code, but fast one, but still why not to improve to the sane degree?
@@DeathSugar While I do agree making things more readable helps in general, I think someone that is familiar with binary search will immediately understand what things like "r" and "l" stand for. Especially after he mentions what they are in the video.
@@DinujayaRajakaruna problem not with understaning. It uses "magic" evaluation to prevent from violating boundries - thats where I messed up with the 1/l.
@@DeathSugar it's not "magic" though, m = l + floor((r-l)/2) is exactly how you calculate the midpoint of l and r without getting any overflow issues. The standard way is m = floor((l+r)/2) but if l and r are large enough this overflows. He mentions this in the video, and this fact is mentioned in the Wikipedia page for binary search as well.