Find Peak Element

[scnullois]

Hey Kevin, I think you should spend more time explaining why this is the solution. The explanation of why you are doing it this way is definitely non-trivial but it goes something like this: The logarithmic complexity is a big clue that you have to use binary search. However, understanding what to do and why is more tricky than first meets the eye. The key point is that the point beyond the end points are anchored to minus infinity which guarantees going beyond endpoints is downhill. That means that if we are able to get to any of the endpoints in uphill direction, then that endpoint is a peak since just beyond it is downhill to minus infinity. Therefore, if the endpoints are not peaks, then we must be traveling down to them. Now, if we pick a random point in between, and follow it in the up direction, at some point it has to hit a peak and go downhill to an endpoint

[elinaz]

Q1: why this question can use binary search?
A1: Because the question precondition is nums[0] and nums[n] are assumed as infinite, then both of the starting and ending are regarded as an ascending line, there must be a peak point. If nums[mid] > nums[mid+1], then we know there must be a peak in [left, mid] (mid still may be a peak element), otherwise the other part of the line must have a peak point. In another way, binary search means you have a condition can discard half of the searching range. This case satisfies the condition, so we can use BS.

Q2: why only compare nums[mid] and nums[mid+1] instead of nums[mid-1]?
A2: Because mid always is the element nearby left not right, let's imagine if the array only has two elements [1, 2], then mid = 0, mid-1 = -1 which is out of index, but (mid+1) won't cause the problem at all.

Q3: why left = mid +1, but right = mid?
A3: Imaging a hill, if nums[mid] < nums[mid+1], then it's a uphill, we already know nums[mid+1] is bigger, so nums[mid+1] is possible to be the peak, so left = mid + 1. If nums[mid] > nums[mid+1], then this is a downhill, nums[mid] is bigger, so it is possible to be the peak in [left, mid], it's why right = mid.

Q4: why the loop condition is "left < right" instead of "left <= right"?
A4: Because "left = mid+1 or right = mid", this is different from the original BS code “left = mid + 1 or right = mid - 1", so the stop situation is very different. In original BS code, stop situation is left = right + 1, so loop condition is left <= right is reasonable. But in this case, after using some test cases to try, we can see the stop situation is always left == right, so the loop condition is left < right.

Q5: why return left but not others?
A5: In Q4, I explained the stop condition is left == right, so actually both of return left and right are correct (I ran this in LeetCode, pass). Eventually the BS will find the peak point, we only have one element left in array, so the only one element should be the peal point, then return.

All these answers are inspired by the previous comments, if anything wrong please point out, thanks!

[sarthakbhatia]

Imagine it as climbing a peak. Now the left and right ends are at -infinity and there is no plateau so there is a peak to be guaranteed. Now check the middle element, if the next element is less this means that we are on our downward journey in the peak, so the peak is at the left part i.e end=mid (Note:This element might be the peak as the next element is less therefore we included it).And if the next element is greater than the current, this means that we are climbing the peak therefore peak happens to be on the right part(Note:This element can't be the peak).So s=mid+1

[sneakyorange]

Maybe I'm just slow but i found it hard to understand why this works. I think i figured it out: when you check the middle, if the element on the left subarray is greater than the middle element we know that it either continues to grow and reaches a peak at the end of the subarray (since the bounds are -inf), or it eventually shrinks. Either way, we know that there must exist a peak on the left. The same is true for the right subarray.

[rachitgupta]

The idea is that, when you are at the middle element and you see the next element is above you(imagine this as a hill),
you bring left(pointer) to this (mid+1) convinced that since element at mid is less, so element at mid+1 can be a peak, we just have to confirm with the right pointer.


and hence the while loop goes till (left<right)...

[RanjuRao]

Hey, you might also need to tell why we are returning left ! you may want to explain a little bit more on why the solution by taking test case 1 or 2, instead of just writing code. Coding is easy once you understand the concept/idea behind solving the problem. You need to focus on "why we are using this solution" rather than just explaining while coding.

[jeffcarey]

I think there were important clues that are easy to overlook that are key to solving this problem:
1) a[i] != a[i+1] for all i (=> no plateaus, so one element will always be less than or greater than its neighbors)
2) The edges of the array are both -infinity (=> For the all ascending or all descending case, the last or first elements respectively will be peaks)

You could try looking at random nodes, but the problem says log n and we need a systematic way to get to a solution. Use binary search with left and right indices.
1) Look at the mid. Look at its neighbor to the right (mid+1).
1L) Is a[mid+1] higher? Good. This is a potential peak. (We don't know about its right side yet). Let's make it the left since that is what we will eventually return. I call this result an "L".
1R) Is a[mid+1] lower? Let's make right the mid since we know its right-side neighbor is shorter. I call this result an "R".
2) Repeat step 1. This might seem strange but consider the terminal conditions.
2LL) (Step one you picked left, then you did so again this time). If the new a[mid+1] is higher, you will basically throw away the potential peak you found in step 1 and using this new one instead. You aren't really any worse off than you were before though. You will eventually get an "R", or in the worst case (all ascending) you will pick the last element since a[n] = -inf.
2LR) You picked left the first time, right this time. You are holding on to the potential peak you found, and "reeling in" the right pointer. If you were able to repeatedly do this, on the last step you will have determined that the element to the right is lower, left will then equal right and you know you have a peak.
2RR) Your left pointer is still at the beginning, we are reeling in the right index. Either you will eventually get an "L" and be in a position similar to 2LR or 2LL, or worst case you have the all descending scenario, and the first index will be considered the peak since a[-1] = -inf.
2RL) You have a potential peak in mid+1, assign to left pointer. Similar to 2LL.

Admittedly, I don't know if I would have come up with this if I saw this problem cold in an interview, without some hints.

[suriveer]

The key to this question is that we have to find any peak and that left and right are - infinity. Consider two test cases : [1, 2, 9, 10, 11eand [1, 12, 9, 10, 11]. In the first test case, there is no such element in the array which is greater than both its neighbors so the answer would be the index of 11 which is 4 but check the next test case there is an element "12" which is clearly grater than both its neighbors but still the above solution will return the index of number 11 which is 4. while a linear solution will return the element 12.

[soumyasengupta]

One of the best questions on binary search

[pistachios]

You said with binary search "we only have to go through half the elements", which is totally wrong. Going through half the elements will still give you linear time solution, using binary search you actually only need to check logn elements.

[YashRaithatha]

It won't work if any one of the left or right half is in increasing sequence unless there is a condition which says that the last or first element can be considered peak if only one of its neighbours (second last or second) is smaller than itself.

[jamalsharif]

i dont think this solution is correct for all the cases coz list is not sorted and we are ignoring complete half of our dataset based on middle values which is wrong.

[akashg]

does he loop from left<right instead of left "<=" right because the upper bound of the array is infinite?

[hunterhe]

Image that you're climbing, you keep climbing to the higher neighbor hill to find a Peak .

[speedrouter]

im still confused.. please help.. is binary search prerequisite is elements being sorted right? ...then how did u choose binary search? Even after u chose how did it work like magic

[munjal]

1, 2, 1, 3, 5, 6, 7 : won't it will fail here ?

[yunlin]

the requirement says any peak is fine. so if value[middle] < value[middle+1], it means at least a peak exists on the right hand side. using binary search it's just because complexity is O(logn)

[Amer]

My linear and binary search ended with same run time :\. I'm assuming the test cases are too small for this example.

[DonchenkoNadia]

Kevin, Thank you for prepared video. For me also not obvious that it is a binary search task... But it works :) Below is the Python version:
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
while (left < right):
mid = left + (right - left)//2
if nums[mid] < nums[mid+1]:
left = mid + 1
else:
right = mid

return left

[paneerlovr]

Would be great to explain how to get to a solution. It’s obvious you just saw the solution, and then just made a video typing it up. You hardly explained why the solution works.