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
00:03 Finding peak element in an array of integers. 01:33 Determining peak element using binary search 02:53 Modified binary search for finding peak element 04:22 Identifying peak elements in binary search 05:41 Monotonic sequence guarantees existence of peak element 07:07 Identifying the peak element in a list using binary search algorithm. 08:26 Calculating the Midway point to avoid overflow. 09:48 Finding peak element using binary search in Python Crafted by Merlin AI.
@@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.
Same approach, alternate code: def findPeak(nums): l , r = 0, len(nums)-1 nums.append(-float('inf')) while l < r: m = (r + l)//2 if nums[m+1] > nums[m]: l = m + 1 else: r = m return l
It's very simple question but I got stuck on point how to check this is index out of bounce. I made solution but it works only if peaks not edge element at index 0 and index len(array)-1. Very good trick to check is mid>0 when try to compare with mid-1 element. It helps me a lot.
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
I was initially confused by that too, but I think what he was just saying is “if mid is already the first element, is there a greater left element that requires us to update our right pointer?” The answer to that is no, we do not have a greater left element when mid is the first element, so don’t update our right pointer, so just return the mid index.
We can just return the mid index = 0 in this case because the fact that the current mid = 0 means: whatever the first element is, it is greater than the right neighbor and the “-inf” left neighbor
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 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.
ruclips.net/video/HtSuA80QTyo/видео.html MITx 6.006 if you want a deeper understanding on Peak Finding. Professor Devadas also talks about 2D Peak Finding.
For some reason m = l + ((r - 1) // 2) wasn't passing all of the testcases. However, changing it to "m = (l+r) // 2" worked and passed all cases. Anybody got any explanations?
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?
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
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.
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
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
@@tuandino6990 still it would be challenging to approach with binary seach
yeah its quite easy
@@yashshukla1637 so then why did you look up the video lmao shut up
@@yashshukla1637 Not quite. Modifying a binary search becomes tricky if one has not seen the question before, in my opinion
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.💝💝
How much time did it take to build it?
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
If you're looking for todays daily LC (design browser history) 👉ruclips.net/video/i1G-kKnBu8k/видео.html
00:03 Finding peak element in an array of integers.
01:33 Determining peak element using binary search
02:53 Modified binary search for finding peak element
04:22 Identifying peak elements in binary search
05:41 Monotonic sequence guarantees existence of peak element
07:07 Identifying the peak element in a list using binary search algorithm.
08:26 Calculating the Midway point to avoid overflow.
09:48 Finding peak element using binary search in Python
Crafted by Merlin AI.
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.
Same approach, alternate code:
def findPeak(nums):
l , r = 0, len(nums)-1
nums.append(-float('inf'))
while l < r:
m = (r + l)//2
if nums[m+1] > nums[m]:
l = m + 1
else:
r = m
return l
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
beautiful explanation! Love it! Thank you! I was so confused, before watching the video!
dude best explanation so far
Awesome explanation
It's very simple question but I got stuck on point how to check this is index out of bounce. I made solution but it works only if peaks not edge element at index 0 and index len(array)-1. Very good trick to check is mid>0 when try to compare with mid-1 element. It helps me a lot.
Great explanation, thanks
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
I was initially confused by that too, but I think what he was just saying is “if mid is already the first element, is there a greater left element that requires us to update our right pointer?” The answer to that is no, we do not have a greater left element when mid is the first element, so don’t update our right pointer, so just return the mid index.
We can just return the mid index = 0 in this case because the fact that the current mid = 0 means: whatever the first element is, it is greater than the right neighbor and the “-inf” left neighbor
I think he meant to say "if m == 0, is it SMALLER than a left neighbor" (i.e. is there a peak to the left of it? No)
if m = 0, there is no m-1 to check, and if m=len(nums), there is no m+1 to check
Great Explanation.
thank you...built the intuition
I don't know how you make it look pretty simple🙂
In binary search questions, within the while loop: When do we use '
if you return directly from a conditional check on the mid point you use
Perfect 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?
Whenever I solve this problem , "I am peaky blinder" is the song that comes into my mind
Inspiring👍
Thanks.
elegant 👍
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
Thanks for saying "It is not that simple to come up"
U a Peak God
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 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
ruclips.net/video/HtSuA80QTyo/видео.html
MITx 6.006 if you want a deeper understanding on Peak Finding. Professor Devadas also talks about 2D Peak Finding.
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.
You are literally the goat.
the code doesnt seems right anymore, they chanaged the question ?
For some reason m = l + ((r - 1) // 2) wasn't passing all of the testcases. However, changing it to "m = (l+r) // 2" worked and passed all cases. Anybody got any explanations?
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
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
So basically we just guessing on which side we gonna have the peak?
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
Python int don't overflow
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
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.
Will you merry me just say yes.
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.
great explanation