Find Peak Element - Leetcode 162 - Python

0:00 - Read the problem
0:45 - Drawing Explanation
8:05 - Coding Explanation

leetcode 162

#neetcode #leetcode #python

[mirceafeder]

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

[vasujhawar.]

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

[donotreportmebro]

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

[harshalyallewar]

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.

[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

[ngneerin]

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

[anujsingh-ejvb]

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?

[srinivasasowmiyan]

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

[letscih]

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

[krzym]

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

[neiljohn]

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

[ghost_assassinz]

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?

[anonanon]

MITx 6.006 if you want a deeper understanding on Peak Finding. Professor Devadas also talks about 2D Peak Finding.

[aryansudan]

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

[erensolmaz]

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

[mayanksingh]

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

[antonr]

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.

[evangelion]

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?

[yuurishibuya]

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.