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
Agree with this comment. I think a lot of these videos are about as useful as publishing the source code with very little commentary. I appreciate the effort that goes into producing them but I think more consideration needs to go into explaining why things are working because it is not always immediately obvious to everyone. I do think this is a common problem in the computer science community however as I've seen the same problem on similar videos by other creators.
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
You say "If nums[mid] > nums[mid+1], then we know there must be a peak in [left, mid]" but what if I have this? [1, 2, 3, 2, 1, 8, 4]? Mid starts out as 2, and is greater than the next element 1. Except the peak is on the right with 8 as the element.
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
Isn't it compulsory for the array to be sorted just so we can use binary search? And if it is sorted last element is peak? I know this is not how BS is used in this question but it confused the hell out of me.
@@Mrbotostyyes it's abs correct that we can apply bs only in a sorted array. But if you think,it is clearly given to find any one peak. In thst case we will be having a sorted aaray. That's why bs worked here.
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.
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
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.
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.
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.
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.
I don't understand this input {1,2,3,2,5,6,7,8,9,9} doesn't work? How can it find the only peak 3 if binary search cuts off the left half of the array? Someone please help
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.
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)
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
The idea here is that the array is definitely sorted up to a point (pun not intended) so we can leverage binary search. Does that make sense? If it doesn't please let me know and I can explain further! :)
it's not a prerequisite, the key to this WHOLE THING is that it's -infinity on either side of the array. so if you find the slope is downhill or uphill based on the middle element, you are guaranteed to find a peak by going up that hill, because it HAS To drop to minus infinity eventually. the binary search just helps you with better "guesses" in the meantime, so to speak.
@@prakad97 , Yes, it goes right, but as the right end will have negative infinity, so it will return 6. Basically in this solution element at index 6 is the peak one
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.
Hi Kevin Thank you very much for these video.These are really helpful. I think above solution will not work for this [1,2,1,3,4,5,6,7,8] ? It looks like we will be looking only into right side of array. please suggest
I was confused as well until I noticed this line in the question: "You may imagine that nums[-1] = nums[n] = -∞. " So in your example, "8" would be valid because on the left is "7" and on the right is (we pretend) negative infinity
It's fine, because we will be traversing towards the last index of the array , and the question says element after the last index -infinity, hence last index will be the answer. Logic is that we know we are moving towards an upward trend and we need to find a downward trend somewhere towards the right, if not then last index is the answer. Also if there are multiple peaks then we can return any one, hence index 1 is not the only answer.
@@KevinNaughtonJr Hi Kevin, Can you please give some examples where this overflow situation can occur, I always thought that left + (right - left) / 2 is done to prevent negative higher rounding. A couple examples would help !!!
@@AbhishekTripathi007 If both right and left were greater than half of the size of the max possible number. Adding them together temporarily would give you a number greater than the max possible number.
this code in python is a = int(input()) array = [] for i in range(a): b = int(input()) array.append(b) try: for i, k in enumerate(array): if array[i+1] > array[i] and array[i+1] > array[i+2]: print(array.index(array[i+1])) except: pass #let me know is there any wrong in this one
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
peek is for the highest value before it goes back down to a lower one. you can have multiple of those but only one of them could be a maximum value. Ex: [1,2,3,7,4,5,10,8,9,20,3] Peek numbers: 7,10,20. max: 20. Hope this helps!!
You explain the naive solution and then explain a better one and then code it out and it takes 4:53 minutes, I come up with a solution and code it out and that takes 30 minutes. Life is not fair :D
The whole array is not sorted, but in a sequence of random numbers, there must be a trend of up and down of numbers, so the array can be said to consists of a number of continuously increasing ranges and continuously decreasing range. So in the continuously increasing range, binary search will work. Don't overthink it, the only thing matter is that we know some range of the array is sorted.
@@xiaotingfu9687 I don't think that's what he meant. binary search only works on either sorted and rotated array. rotated means the sorted array values are moved in order fashion. but I don't get the impression that the problem implies that the array is sorted or rotated from the statement. edit: maybe the statement of nums[-1] = minus infinity give that away
Hey, if the question is to return the first peak, does this approach still work? For eg: inputs: nums = [1,7,1,3,5,6,4] and we are using binary search mid index will be 3 and we check 3
For some reason, I could not for the life of me to get this solution working in javascript; This is the solution I came with. We can simply return the mid if its value is greater then its left value and right value ```var findPeakElement = function(nums) { let left = 0 let right = nums.length - 1 if(nums.length === 1) return 0 while(left nums[mid - 1] && nums[mid] > nums[mid + 1]){ return mid }else if(nums[mid] < nums[mid + 1]){ left = mid + 1 }else { right = mid - 1 } } return left };```
well the loop ends when left==right, so you can return either left or right. The reason why left or right contains the answer is to look back at last iteration. In last iteration either left index(left=mid+1) reaches to right or right reaches to left(right=mid-1) and in either case we made sure the fact that all elements right are lesser too. and when they meet is the peak point. I hope it makes sense
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.
that's the case where the peak is at either side, if the peak is at either side, left will be equal to right equal to mid, in fact, when i solved this on my own (just this morning), i put the condition while (start != end) and it works just fine, i found the problem at MIT freecourseware, i'm starting to slowly understand the intuition why this approach even works.
i might have misunderstood something, the peak was defined if the neighboring elements are less than or equal to it, here it states that there are not duplicates so keep in mind
These videos aren't helpful. If you're going to make a video about a problem, I recommend spending most the time talking about how you came up with the idea and reasoning about it. Your video here isn't any more helpful than reading the top discussion posts.
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
Agree with this comment. I think a lot of these videos are about as useful as publishing the source code with very little commentary. I appreciate the effort that goes into producing them but I think more consideration needs to go into explaining why things are working because it is not always immediately obvious to everyone. I do think this is a common problem in the computer science community however as I've seen the same problem on similar videos by other creators.
@@kashmo7645 Because they probably just looked at the solution and then made a video.
class Solution {
public:
int findPeakElement(vector& nums) {
int start=0;
int end=nums.size()-1;
while(start
kevin bhai maa chod denge jyada bolo mt, agar bolna h to aao kanpur m
@@amirtv106 hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh of course
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
You say "If nums[mid] > nums[mid+1], then we know there must be a peak in [left, mid]" but what if I have this? [1, 2, 3, 2, 1, 8, 4]? Mid starts out as 2, and is greater than the next element 1. Except the peak is on the right with 8 as the element.
@@AK-fb7zn We also have "3" (index 2) as a peak in the left subarray.
I LOVE YOU RANDOM PERSON, I HAVE BEEN STRUGGLING WITH THE EXPLANATION FOR DAYS AND I FINALLY UNDERSTOOD IT, THANK YOU!!!
this is not a good answer. this is a great answer!
wish youtube had an option for bookmarking comments. lol
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
Isn't it compulsory for the array to be sorted just so we can use binary search? And if it is sorted last element is peak? I know this is not how BS is used in this question but it confused the hell out of me.
@@Mrbotostyyes it's abs correct that we can apply bs only in a sorted array. But if you think,it is clearly given to find any one peak. In thst case we will be having a sorted aaray. That's why bs worked here.
What will be the output for
1 2 1 3 5 6 7
Will it be 6 instead of 1? But I think 1 would be the better answer.
@@nikhilaitha6836 yes but maybe we can return any of them as mentioned in the question
@@nikhilaitha6836 yes but maybe we can return any of them as mentioned in the question
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.
This one is tricky!!! The format of binary search is often pretty simple but small curveballs like this make them tough don't be hard on yourself!
Yes, this had me confused for days. I finally understood it through a stackoverflow post
@@ShivangiSingh-wc3gk Nice! Sorry if the explanation wasn't clear, happy to hear you understand it now!
@@KevinNaughtonJr So, we do not have to sort the array first ?
@@jageenshukla4825 Nah we don't, the idea is that the array is sorted up to a point and therefore we leverage binary search
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
that 'imagine this as a hill' part helped me understand this. thank-you!
class Solution {
public:
int findPeakElement(vector& nums) {
int start=0;
int end=nums.size()-1;
while(start
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.
does he loop from left
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.
There is "You may imagine that nums[-1] = nums[n] = -∞."
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.
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.
One of the best questions on binary search
Good one to know!
I have a question. what if i have duplicates in sorted parts. Then should I skip the duplicates till the last occurence?
Image that you're climbing , you keep climbing to the higher neighbor hill to find a Peak .
For this array..[1,2,3,1,2,3,4] here peak is 3 but it will give 4
Prakad Alpha according to the problem description, here 4 can also be the peak element since 4>3 and also 4> -infinity
My linear and binary search ended with same run time :\. I'm assuming the test cases are too small for this example.
Yep, no real difference in so small inputs
beautifully explained
I don't understand this input {1,2,3,2,5,6,7,8,9,9} doesn't work? How can it find the only peak 3 if binary search cuts off the left half of the array? Someone please help
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.
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)
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
The idea here is that the array is definitely sorted up to a point (pun not intended) so we can leverage binary search. Does that make sense? If it doesn't please let me know and I can explain further! :)
@@KevinNaughtonJrHi Kevin..I guess this array [1,2,3,1,2,3,4] it goes right but the peak is at 3..am I wrong?
it's not a prerequisite, the key to this WHOLE THING is that it's -infinity on either side of the array. so if you find the slope is downhill or uphill based on the middle element, you are guaranteed to find a peak by going up that hill, because it HAS To drop to minus infinity eventually. the binary search just helps you with better "guesses" in the meantime, so to speak.
@@prakad97 , Yes, it goes right, but as the right end will have negative infinity, so it will return 6. Basically in this solution element at index 6 is the peak one
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.
A question, what happens if the array is not sorted? Are we going to have O(n)?
What happens If we have peek element is before mid?
1,3,1,2,3,4,5,6,7,8 = 3 is peek but it won't be checked as mid compared with mid+1
Simply beautiful !
Hi Kevin
Thank you very much for these video.These are really helpful.
I think above solution will not work for this [1,2,1,3,4,5,6,7,8] ?
It looks like we will be looking only into right side of array.
please suggest
I was confused as well until I noticed this line in the question:
"You may imagine that nums[-1] = nums[n] = -∞.
"
So in your example, "8" would be valid because on the left is "7" and on the right is (we pretend) negative infinity
It's fine, because we will be traversing towards the last index of the array , and the question says element after the last index -infinity, hence last index will be the answer. Logic is that we know we are moving towards an upward trend and we need to find a downward trend somewhere towards the right, if not then last index is the answer. Also if there are multiple peaks then we can return any one, hence index 1 is not the only answer.
@@tubedaputtar You nailed it. Basically, move towards upward trend.
@@marklarr Thanks for the explanation
Can you explain why you didn't use (left + right)/2 to find the mid point? Thanks 😊
doing left + (right - left) / 2 helps prevent overflow if you're given really large arrays :)
@@KevinNaughtonJr Thanks for the reply!
@@KevinNaughtonJr Hi Kevin, Can you please give some examples where this overflow situation can occur, I always thought that left + (right - left) / 2 is done to prevent negative higher rounding. A couple examples would help !!!
@@AbhishekTripathi007 If both right and left were greater than half of the size of the max possible number. Adding them together temporarily would give you a number greater than the max possible number.
this code in python is
a = int(input())
array = []
for i in range(a):
b = int(input())
array.append(b)
try:
for i, k in enumerate(array):
if array[i+1] > array[i] and array[i+1] > array[i+2]:
print(array.index(array[i+1]))
except:
pass
#let me know is there any wrong in this one
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
This code is not working on Leetcode
class Solution {
public:
int findPeakElement(vector& nums) {
int start=0;
int end=nums.size()-1;
while(start
1,2,1,3,5,6,7 : won't it will fail here ?
Yes it will fail.
No. 7 is correct ans. Because, You may imagine that (nums[-1] = nums[n] = -∞).
@@Igloo11 yeah correct. I realized this later. Thanks
What if the peak is present in the left sub array. example - {1,2,1,3,4,5,6}. Is index 1 not the peak, but with this logic we will get 6.
I am wondering what is the difference between finding peak element or max element in array
peek is for the highest value before it goes back down to a lower one. you can have multiple of those but only one of them could be a maximum value. Ex: [1,2,3,7,4,5,10,8,9,20,3] Peek numbers: 7,10,20. max: 20. Hope this helps!!
You explain the naive solution and then explain a better one and then code it out and it takes 4:53 minutes, I come up with a solution and code it out and that takes 30 minutes. Life is not fair :D
its not complicated, at the u will find pure increasing or decreasing sequence guarateed to find peek element
But how do we know that the array is sorted? Am I missing something obvious?
The whole array is not sorted, but in a sequence of random numbers, there must be a trend of up and down of numbers, so the array can be said to consists of a number of continuously increasing ranges and continuously decreasing range. So in the continuously increasing range, binary search will work. Don't overthink it, the only thing matter is that we know some range of the array is sorted.
@@xiaotingfu9687 Ok cool. Is that because the numbers are simulating a mountain range so to speak?
@@xiaotingfu9687 I don't think that's what he meant. binary search only works on either sorted and rotated array. rotated means the sorted array values are moved in order fashion. but I don't get the impression that the problem implies that the array is sorted or rotated from the statement.
edit: maybe the statement of nums[-1] = minus infinity give that away
Hi. @Kevin Naughton Jr. Thanks for the solve. should not it be - if nums[mid]
he corrected at the end , see whole video.
hey can you increase your voice tone a bit because it gets difficult to understand what you said at times . thanks !
Exactly
Hey, if the question is to return the first peak, does this approach still work?
For eg:
inputs: nums = [1,7,1,3,5,6,4]
and we are using binary search mid index will be 3 and we check 3
That's okay because you can still return 6. The problem says that you may return any of the peak.
@@manojadhikari2290 Yeah, but I was asking if the question was to return the first peak. this wouldn't work.
@@neevanyI see. You're right, it won't work for that case.
For some reason, I could not for the life of me to get this solution working in javascript;
This is the solution I came with.
We can simply return the mid if its value is greater then its left value and right value
```var findPeakElement = function(nums) {
let left = 0
let right = nums.length - 1
if(nums.length === 1) return 0
while(left nums[mid - 1] && nums[mid] > nums[mid + 1]){
return mid
}else if(nums[mid] < nums[mid + 1]){
left = mid + 1
}else {
right = mid - 1
}
}
return left
};```
hhhhhhhh finaly no hash set this time
reading code != explanation
Why do we return left? What's is intention in that can anyone explain me? Thanks in advance!(:
well the loop ends when left==right, so you can return either left or right. The reason why left or right contains the answer is to look back at last iteration. In last iteration either left index(left=mid+1) reaches to right or right reaches to left(right=mid-1) and in either case we made sure the fact that all elements right are lesser too. and when they meet is the peak point. I hope it makes sense
@@sanjeev0075 thanks man👍
one of the best explanation of this question, that explains why each step was taken and why binary search was chosen.
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.
Why not right = mid -1
This code is not working on Leetcode
class Solution {
public:
int findPeakElement(vector& nums) {
int start=0;
int end=nums.size()-1;
while(start
why not simply approach this with this easy logic:
public static int findPeak(int[] num){
if (num[0] >= num[1])
return 0;
if (num[num.length - 1] >= num[num.length - 2])
return num.length - 1;
for(int i=1;inum[i-1]&& num[i]>num[i+1]){
return i;
}
}
return -1;
}
"Hopefullly we should just have to return 'left' ". I wish you would have explained that, instead of calling it 'hopefully'.
that's the case where the peak is at either side, if the peak is at either side, left will be equal to right equal to mid, in fact, when i solved this on my own (just this morning), i put the condition while (start != end) and it works just fine, i found the problem at MIT freecourseware, i'm starting to slowly understand the intuition why this approach even works.
i might have misunderstood something, the peak was defined if the neighboring elements are less than or equal to it, here it states that there are not duplicates so keep in mind
can you please address clone graph problem "leetcode.com/problems/clone-graph/" . Please upload a video for the same
public int findPeakElement(int[] nums) {
int startIndex=0, endIndex = nums.length-1;
while(startIndex
Spoil Alert: You only need to return one of the peak values, not all of them as a peak value list.
Wow ! Nice explanation & Nice solution.
Love from Bangladesh !
Btw im 15 .
typing out code without any real explanation of the approach. try giving more detailed explanation coz this helps no one, its just plain waste of time
Bizzare Explanation 🥴 Beginners Unsubscribe ❗
return nums.index(max(nums))
These videos aren't helpful. If you're going to make a video about a problem, I recommend spending most the time talking about how you came up with the idea and reasoning about it. Your video here isn't any more helpful than reading the top discussion posts.