FINDING A PEAK

Hello, there!

As developers, we are constantly learning and implementing something or the other, taking cues from different people, their methods of thinking and creating so as to arrive at the most efficient solution to a problem. I am no different. Here, as I welcome you to the first post of this series on algorithmic thinking, we will explore some classic problems and delve into finding efficient procedures for solving them. The motivation for this series comes from MIT 6.006 Introduction to Algorithms, Fall 2011 course which I stumbled upon yesterday and this series will serve as a means of documenting my journey and helping you along the way. So, without further ado, let’s begin.

Problem Statement:

Given an array of integers, find a peak element.

What is a peak element?

An array element is a peak if it is not smaller than its neighbours.

eg: Consider the following array,

Here, we have given symbols a, b, c and so on to this array of integers. For the sake of simplicity, we will assume that these are positive integers.

For an integer at position 2 to be a peak, it should not be smaller than its neighbours, which means b ≥ a and b≥ c.

In case of edges, you need to look to only one side, e.g: in case of position 9 to be the peak, i ≥ h.

You must have also seen that the problem talks about returning a peak.

Lets look at an array of integers and find a peak:

A = {10, 20, 15, 60, 45, 90}

Here, we have three peaks, 20, 60 and 90 (if you don’t understand how, read the part again where I define what a peak element is.) But since our problem talks about finding ‘a’ peak, we can happily return any one of them and successfully solve the problem.

Now that you have some basic understanding of what a peak is, let’s approach the problem. But before that, let’s look at some corner cases here,

  1. If our input array is sorted in an ascending order, say {10, 15, 20, 45, 60, 90}, then the peak element will always be at the end. In this case, its 90.
  2. If our input array is sorted in a descending order, say {90, 60, 45, 20, 15, 10}, then the peak element (90 in this case), will always be at the beginning.
  3. And if all elements of the input array are same, i.e.; {3, 3, 3}, then according to our definition, every element is a peak element.

SOLVING THE PROBLEM:

There are always two roads leading to the solution. One that is simple but not necessarily the best and the other which might not be your first idea, but will turn out to be the best idea. And like all humans, we will look at the stupid idea first to appreciate the better one.

Straightforward Algorithm:

Let’s assume that in an n element array, the element at the n/2 th position is our peak element, so the numbers start increasing from the left to the middle, where they reach their highest and then they start decreasing after that point.

This algorithm will look at n/2 elements by starting from the left and moving towards the middle to find a peak.

But, what if the input array is sorted in a strictly increasing order, which means that we would need to traverse the entire array, and reach upto the last element in an array to find a peak.

This implies that in an array sorted strictly in an increasing order containing n elements, we would need n iteration to find the peak.

So, the worst case time complexity here will be a 𝚹(n).

Can we do better than a linear time complexity?

To answer this question, we need to take the road less taken like Robert Frost did. That’s the only way to find out if it makes a difference.

Divide and conquer:

The idea is Binary Search based. We will look at the middle element, i.e., the element residing at the n/2 position.

  1. If the middle element is not smaller than any of its neighbours, voila! You have found the peak. Now is the time to bask in glory.
  2. Otherwise, if the middle element is smaller than its left neighbour, there exists a peak in the left half.
  3. Else, if the middle element is smaller than its right neighbour, the peak exists in the right half.

(If you don’t understand why, take a few examples.)

Given below is an implementation of this function,

Let’s look at the time complexity for this problem,

The recurrence relation to this problem can be written as,

T(n) = T(n/2) + 𝚹(1)

For an input size of n, T(n) amount of work is done. 𝚹(1) corresponds to the two comparisons that we do ( two comparisons being constant hence represented with 𝚹(1)).

So we take the above equation and expand it eventually we will get to the best case which is T(1) = 𝚹(1).

So we could also write the equation as

T(n) = 𝚹(1) + …… + 𝚹(1) [This is a expanded form of the above equation]

We will expand it log n times. So the complexity of the algorithm is (log n)

Find the complete swift implementation on: https://gist.github.com/VasudhaJha/dd53153bafd088633edfb94027ba7580

To get a detailed classroom experience regarding the problem, go to: Algorithmic Thinking, Peak Finding Video

Find the lecture notes and the screenshots used in this blog at: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Vasudha Jha

An engineer, artist and writer, all at the same time, I suppose.