Problem Explanation

We are given a mountain array, i.e., an array that first increases and then decreases. Our task is to find the peak of this mountain which is the index of the largest element in the array. By the problem constraints, we know that there exists a peak in the given array for sure.

In a more general sense, we can make a few key observations. By nature of the problem, we can state two important points:

• All elements to the left of the peak element are in ascending order.
• All elements to the right of the peak element are in descending order.

We can use these two observations to come up with a solution for the problem.

Walk through an example

Let's consider an input [0,2,1,0]. This an array in 'mountain' structure where, the elements initially increment to reach a peak and then decrement. Here peak is at index 1 which is 2. The output should be the index i.e 1.

Solution approach

This problem can be solved using Binary Search.

Since the elements of the array rise to a peak and then fall. If a mid element, arr[m], is less than its immediate next element, arr[m+1], that means the peak is towards the right, so we change the low pointer to mid+1. On the contrary, if a mid element is greater than its next element, peak is towards the left, and we change the high pointer to mid.

The binary search is a divide and conquer algorithm. In a loop we take two indexes, left and right. Calculate the mid = (left + right) / 2 index and check the two adjacent numbers: mid and mid+1. If the mid number is less than mid+1, then the mountain peak cannot be in the left part, move the left index to mid. Otherwise, the mountain peak cannot be in the right part, move the right index to mid. The loop will stop when left == right and returns the mountain peak index.

Python Solution

1
2python
3class Solution(object):
4    def peakIndexInMountainArray(self, arr):
5        left, right = 0, len(arr) - 1
6        while left < right:
7            mid = (left + right) // 2
8            if arr[mid] < arr[mid + 1]:
9                left = mid + 1
10            else:
11                right = mid
12        return left

Java Solution

1
2java
3class Solution {
4 public int peakIndexInMountainArray(int[] arr) {
5    int l = 0;
6    int r = arr.length - 1;
7
8    while (l < r) {
9      int m = (l + r) / 2;
10      if (arr[m] < arr[m + 1])
11        l = m + 1;
12      else
13        r = m;
14    }
15
16    return l;
17  }
18}

Javascript Solution

1
2javascript
3class Solution {
4 peakIndexInMountainArray(arr) {
5    let l = 0;
6    let r = arr.length - 1;
7
8    while (l < r) {
9      let m = Math.floor((l + r) / 2);
10      if (arr[m] < arr[m + 1])
11        l = m + 1;
12      else
13        r = m;
14    }
15
16    return l;
17 }
18}

C++ Solution

1
2c++
3class Solution {
4public:
5    int peakIndexInMountainArray(vector<int>& arr) {
6        int l = 0;
7        int r = arr.size() - 1;
8    
9        while (l < r) {
10            int m = (l + r) / 2;
11            if (arr[m] < arr[m + 1])
12                l = m + 1;
13            else
14                r = m;
15        }
16    
17        return l;
18    }
19};

C# Solution

1
2csharp
3public class Solution {
4    public int PeakIndexInMountainArray(int[] arr) {
5        int l = 0;
6        int r = arr.Length - 1;
7
8        while (l < r) {
9            int m = (l + r) / 2;
10            if ( arr[m] < arr[m + 1])
11                l = m + 1;
12            else
13                r = m;
14        }
15
16        return l;
17    }
18}

All the presented solutions follow the binary search approach, taking advantage of the mountain array's property for locating the peak efficiently. By comparing the middle element and its adjacent element, the solutions narrow down the search area by half every time, leading to a logarithmic time complexity.

All considered solutions follow the same approach and logic, albeit in different programming languages, demonstrating the problem's universality and the power of binary search for tackling such problems.

This problem is a wonderful illustration that understanding and deploying suitable algorithms is not just language-specific, but a universally applicable skill in problem-solving. With binary search, we can solve this problem in an efficient manner with a time complexity of O(log n), which is significantly better than the linear scan approach.

This technique can also be applied to many related problems, such as finding an element in a sorted and rotated array, finding the smallest or largest element in a sorted and rotated array, amongst others.

Based on our learnings, the key is to visualise and analyse the problem as much as possible before jumping into a solution, which helps in employing suitable algorithms wherever needed effectively. Relying on mathematical tools can significantly improve the efficiency of our solutions, making us better programmers and problem solvers.