Peak element Intuition

Photo by Amith Nair on Unsplash

Your goal is to find the peak element in a given collection of elements.

The peak elements are shown in green

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?

Possibility 1:

An element has two neighbors and both are less than or equal to it. This is then already the peak element.

Green is the current element and blue colored are the neighboring elements

Possibility 2:

A neighbor on the left

One alternative is when you have a single neighbor on the left and the current element is greater than or equal to it.

A neighbor on the right

The other alternative is when you have a single neighbor on the right and the current element is greater than or equal to it.

Possibility 3:

End of happy cases.

Here you have a neighbor on the left that is greater than or equal to the current element.

Green is the current element, blue are the neighbors and yellow are the possible elements for the neighbor that is greater than current.

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.

Get coding !!

This kind of intuition is taught at Scaler Academy, where I am currently enrolled. The ideas in this post were introduced to me by Kshitij Mishra who is an instructor at Scaler.

I hope to post more blogs on problem-solving intuition soon. Stay Tuned!!