Leetcode 852. Peak Index in a Mountain Array
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.