Find Peak Element - Leetcode 162 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/find-pe...
0:00 - Read the problem
0:45 - Drawing Explanation
8:05 - Coding Explanation
leetcode 162
#neetcode #leetcode #python

[@mirceafeder4945]

RIP to all those who got this in an interview without solving it before

[@ssgojekblue]

peak comment

[@vasujhawar.6987]

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.💝💝

[@igorborovkov7011]

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

[@tazveerhossainkhan4856]

Great Explanation.

[@jessanraj9086]

Awesome explanation

[@mayilbayramov2886]

Perfect explanation

[@NeetCodeIO]

If you're looking for todays daily LC (design browser history) 👉czcams.com/video/i1G-kKnBu8k/video.html

[@donovanhood4696]

You are literally the goat.

[@skairways]

Great explanation, thanks

[@m.kamalali]

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

[@takerixgaming4170]

I can't understood bro

[@vukanoa]

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

[@ngneerin]

Go mid
If peak return
If right is greater drop left
If left is greater drop right
Repeat

[@kryptoknight992]

what if both left and right element are grater than mid?

[@ngneerin]

@@kryptoknight992 Go any way depending on which side your program is checking. Both side there is at least 1 peak

[@calvinminnesota5540]

Inspiring👍

[@vikasgupta1828]

Thanks.

[@its_shivam_jha]

thank you...built the intuition

[@jisanson]

elegant 👍

[@anujsingh-ej9vb]

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?

[@srinivasasowmiyan2272]

I don't know how you make it look pretty simple🙂

[@shivamsiddharthasinghrajaw7671]

A greedy binary search if you will

[@user-le6ts6ci7h]

Whenever I solve this problem , "I am peaky blinder" is the song that comes into my mind

[@anonanon2625]

czcams.com/video/HtSuA80QTyo/video.html
MITx 6.006 if you want a deeper understanding on Peak Finding. Professor Devadas also talks about 2D Peak Finding.

[@edwardteach2]

U a Peak God

[@ghost_assassinz1877]

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?

[@ghost_assassinz1877]

oh I didnt read one of the constraints never mind

[@aryansudan2239]

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?????

[@VictorNascimentoo]

You only need to guarantee the side you're looking for has a peak. You can return any peak, not the global max.

[@neiljohn2637]

It won't work for when the list contains the same number throughout right? Coz this code will return m rather None.

[@YuvrajRaghuvanshiS]

Adjacent elements must be different

[@antonr786]

So basically we just guessing on which side we gonna have the peak?

[@alisktl]

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.

[@Pratik-tk6ts]

no two neighbouring numbers are equal, check constraints

[@alisktl]

@Pratik-tk6ts thanks, did not see that constraint

[@andhikaagung2936]

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

[@xrobstar]

The question states that an O(log n) solution is required. Searching for the max element is a linear O(n) solution.

[@evangelion933]

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?

[@practicefirsttheorylater]

read the constraints

[@fantasticallyurs1]

numbers adjacent to each other can't be equal

[@yuurishibuya4797]

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.

[@shamilgurban6439]

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.

[@DeathSugar]

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

[@DinujayaRajakaruna]

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.

[@DeathSugar]

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

[@DinujayaRajakaruna]

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

[@DeathSugar]

@@DinujayaRajakaruna problem not with understaning. It uses "magic" evaluation to prevent from violating boundries - thats where I messed up with the 1/l.

[@DinujayaRajakaruna]

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