Find Peak Element - Leetcode 162 - Python

hey everyone welcome back and let's write some more neat code today so today let's solve the problem find Peak element we're given an array of integers and they don't mention it here it's mentioned all the way at the bottom of the description but it's a very important fact and it is that any two adjacent elements suppose a number at index I and and number at index I plus one these are never going to be equal so any adjacent elements in the array are not going to be equal that's a very important fact for this problem so I wanted to mention it at the beginning we want to find a peak element within this array a peak element is kind of how it sounds so imagine that there are three elements the peak element is the one that is greater than both of its adjacent neighbors now it's possible that there could be multiple Peak elements that's okay we can return any of them so we could return this one or this one now what if our array looks something like this three two one at first glance there aren't any Peak elements in this array but the way they Define Peak elements these endpoint values suppose three it's greater than its right neighbor but it doesn't have a left neighbor so can this be a peak element well the answer is yes any endpoint value like three is implicitly assumed to be greater than its neighbor if its neighbor doesn't exist so if it's left neighbor doesn't exist three is considered to be greater than its left neighbor for one since its right neighbor doesn't exist it's assumed to be greater than its right neighbor now it's not greater than its left neighbor so this is not a peak element but three is a peak element it's greater than this and it's greater than this given those facts we are guaranteed that there's going to be a peak element in this array our goal is to find it it'd be pretty easy to do with a linear scan but they actually want us to do better we want to do this in log n time are there any algorithms you can think of that are login time well pretty much the only one that would work in this case is binary search but is it even possible to run binary search on this problem well let's go back to basics and think about what binary search is as an algorithm we have an array suppose one two three one usually we have a left and right pointer we calculate the Midway Point let's say this is the Midway point we have a pointer here we check is this guy a peak element check its left neighbor well it's greater than it's left neighbor check it's right neighbor it's not greater than its right neighbor so we know for sure this is not a peak element but the idea behind binary search is that we should be able to eliminate half of the search space every single time we should be able to either say okay we know for sure there's no solution on this side so we're going to search on this side or we should be able to say the opposite we know for sure there's no solution here let's search over over here but we can't really say that with this problem there could be a solution here or here and it's actually possible there could be a solution on both sides of the array so let me say this slowly this is going to be a modified binary search where we don't necessarily have to eliminate half of the search space every single time we're just looking for a single Peak element so we just have to be sure that the side that we decide to search on whether it's this side or this side we have to be sure that the side does have a peak element maybe there's a peak element on both sides doesn't matter we just have to be sure that there is one on the side that we're searching if this is not a peak element how do we know which side is guaranteed to have a peak element well let me show you a very simple example let's suppose that our array was monotone chronically increasing so these points kind of represent the values of our array is this a peak Element no is this a peak Element no is this one no is this one yes it is because it's greater than its left neighbor and it doesn't have a right neighbor so this is a peak element so if we were running our binary search on this array and we looked at this point and we saw that this value is not a peak element so we're not going to search here which side do we want to search on the left side or the right side we're going to go on the right side because even though we can't see the entire array we see that it's right neighbor is greater than it so maybe this is a peak element maybe this point doesn't exist and the value is actually somewhere down here so we know this is not a peak element but this is greater than its left neighbor and it's also greater than its right number that's a possibility but even if it's not true even if this value doesn't exist and it's actually all the way up here look it's still guaranteed that there's a peak element because all the way at the right either this is going to be monotonically increasing which guarantees that there's going to be a peak element on this side of the array or it's not monotonically increasing which means one of these points suppose this one is going to be down here or maybe you know there's a few more points and one of those is going to be below so like this one would be all the way down here and in that case it's also guaranteed that this is a peak element as well as this being a peak element can you kind of see the intuition out either this portion of the array is monotonically increasing which guarantees a peak element or it's not monotonically increasing which means that there's going to be a dip somewhere which also guarantees that there's a peak element and that's true because we know for sure that this is not a peak element but its neighbor is greater than it so it's already increasing here and it might keep increasing or it might dip somewhere now the opposite could have been true as well it could have been going downwards it could have been monotonically decreasing so if we looked at this value and saw it's not a peak element which side are we going to decide to search on this side because its left neighbor is greater so we're guaranteed that there's going to be a peak element here because it's monotonically decreasing which means all the way at the left is going to be a peak element or there's going to be a dip somewhere maybe here or maybe here which guarantees that there's going to be a peak element so if we are running binary search and our mid value suppose in this case over here is not a peak element we're going to search on the side that has a neighbor value that's greater and we're guaranteed to have a neighbor value that's greater because if we didn't if this was like one for example and this is 2 and this is one then by definition this is a peak element so if this value is not a peak element we're guaranteed that one of its neighbors are going to be greater than it and that's the side that we're going to search on it's really that simple I know it's probably not simple to come up with but once you understand it it does make a lot of sense so now wrapping our binary search up we're going to take our left pointer and shift it to be mid plus one so it's going to be over here now and then we're going to recalculate the mid pointer to be left plus right divided by 2 which I think is going to be over here so then we're going to check is this the peak element we're going to compare it to its left neighbor it's greater we're going to compare it to its right neighbor it's also greater so this is the solution we return the index in this case I believe yep over here and and since this is binary search it's running in log and time constant memory so now let's code it up so this is mostly going to be a cookie cutter binary search we're going to initialize our left pointer to be zero our right pointer to be all the way at the end length minus 1 and then we're going to have our while loop while our left pointer is less than or equal to right we know for sure that we're going to return within this Loop so we don't really need to put like a return statement out here so I'm not going to bother with that but we're going to calculate the Midway point we could say left plus right divided by 2 but it's possible that that overflows a way to make sure that it never overflows is to do it like this basically take the distance between right and left which is right minus left divide that by two and then add that to the left pointer this is basically another way to calculate the Midway point that just guarantees that it's not going to overflow most of the time you won't need to do this in coding interviews but I think gets helpful to know how to do it now we're going to check is the left neighbor greater than the value at index M how do we check that well basically check the value at index m is less than its left neighbor at M minus 1. if that was true we would say we're going to search on the left side so we say our right pointer is going to be mid minus 1. now there's one catch here there's one Edge case what if m is equal to zero in that case is it greater than its left neighbor no so we are going to check that m is greater than zero it's not equal to zero it's greater than zero and this is true that also helps us because then we will never get an index out of bounds error here and we can do the same thing to check if it's right neighbor is greater so I'm going to copy and paste the above and just change it up a bit instead of of checking if m is greater than zero we're going to check if m is less than the rightmost position of the array which is length of nums minus one and the value right of it which is not M minus 1 it's M plus 1 is greater than it so if this is true if it's right neighbor is greater that means we're going to search on the right side so we're going to say left is equal to M plus 1. so we have the two cases where we're either going to search on the left side or on the right side but if we don't do either of these that means we for sure found the solution so else is the case where we found the peak element and we want to return the index which is M so that's the entire code now let's run it to make sure that it works and as you can see yes it does and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neat code.io it has a ton of free resources to help you prepare thanks for watching and Hope hopefully I'll see you pretty soon