Peak element Intuition
Your goal is to find the peak element in a given collection of elements.
If an element is greater or equal to its neighbors then it can be considered as a peak element.
The naive approach is to just iterate through all the elements and find the element that is greater than or equal to its immediate neighbor as described in the question.
What if I could randomly pick any element, can something be said about that element from checking its neighbors?
An element has two neighbors and both are less than or equal to it. This is then already the peak element.
One alternative is when you have a single neighbor on the left and the current element is greater than or equal to it.
The other alternative is when you have a single neighbor on the right and the current element is greater than or equal to it.
End of happy cases.
Here you have a neighbor on the left that is greater than or equal to the current element.
Can we safely move to that greater neighbor, hence, making a decision to eliminate the current element and all neighbors on the right?
Let’s find out. If yellow-colored elements are the two probable neighbors of the greater neighbor. Then if the below yellow neighbor is considered, then we can say this blue element is the peek, or else we can extend the same reasoning to the other greater yellow neighbor, where the blue element becomes the green element (current) and the greater yellow neighbor becomes the blue element (greater neighbor). Therefore, we can conclude, that the greater neighbor side should definitely have a peek element.
If this reminds you of the binary search, then you are spot on, as we are similarly eliminating half the search space in each step.
This is the intuition behind finding a peak element in a collection. Will a peak element always exist? Definitely, as there has to be a maximum element.
The code should not be a big leap from here.
I hope to post more blogs on problem-solving intuition soon. Stay Tuned!!