Find Peak Index in a Mountain Array Solution | Code In C++/Java/Python
Problem Description:
You are given an integer mountain array arr of length n where the values increase to a peak element and then decrease.
Return the index of the peak element.
Your task is to solve it in O(log(n)) time complexity.
Examples:
Input: arr = [0,1,0]
Output: 1
Explanation: All the elements to the left and right of index 1 (value = 1) are smaller hence 1 is the peak, It lies at index one, so we return 1.
Input: arr = [0,2,1,0]
Output: 1
Explanation: All the elements to the left and right of index 1 (value = 2) are smaller hence 1 is the peak, It lies at index 1, so we return 1.
Input: arr = [0,10,5,2]
Output: 1
Explanation: All the elements to the left and right of index 1 (value = 10) are smaller hence 1 is the peak, It lies at index 1, so we return 1.
Constraints:
- 3 <= arr.length <= 10⁵
- 0 <= arr[i] <= 10⁶
- arr is guaranteed to be a mountain array.
Given an array where the values increase up to some index and then decrease until the end. We are supposed to return the peak index of the mountain array.
For now, we will forget about the time complexity and focus solely on solving this problem.
Brute Force Approach
Intuition:
To form the peak index in a mountain array solution. The first idea that comes to mind is to check each index to see if it's the peak. But before we do that, we need to understand what makes an index a peak.
What is the peak condition?
When we visualize the array, it first increases to a certain point and then decreases, like a mountain. From index 0 to some index i, the slope is positive (going up), and from index i+1 to the end of the array, the slope is negative (going down). This index i, where the slope changes from positive to negative, is the peak index, which we need to find and return.
Peak index in a mountain array Solution
For an index to be a peak, the value at that index must be greater than its immediate neighbours on both sides. This condition is enough to determine if an index is a peak because any other index will either be part of the ascending slope or the descending slope.
To find the peak index, we will iterate through the entire array and check each index to see if it satisfies the peak condition. That is, we simply check if the value is greater than its immediate neighbours to its left and right. If it is greater, we will return that index.
Peak index in a mountain array solution example
Input: arr = [1, 2, 3, 4, 3, 1]
Output: 3
Explanation: All the elements to the left and right of index 3 (value = 4) are smaller hence 3 is the peak.
Initial State:
- arr = [1, 2, 3, 4, 3, 1]
- n = arr.size() = 6
Check the First Element:
- Condition: if (arr[0] > arr[1])
- Evaluates to: if (1 > 2) → false
- Since the condition is false, the code moves to the next check.
Check the Last Element:
- Condition: if (arr[n-1] > arr[n-2])
- Evaluates to: if (1 > 3) → false
- Since the condition is false, the code moves to the for loop.
For Loop Iteration: (i=1 to i=n-2) -- (1 to 4)
- Iteration 1 (i = 1):
- Condition: if (arr[i] > arr[i-1] and arr[i] > arr[i+1])
- Evaluates to: `if (arr[1] > arr[0] and arr[1] > arr[2])
- Substituting values: if (2 > 1 and 2 > 3) → false
- If the condition is false, move to the next iteration.
- Iteration 2 (i = 2):
- Condition: if (arr[i] > arr[i-1] and arr[i] > arr[i+1])
- Evaluates to: if (arr[2] > arr[1] and arr[2] > arr[3])
- Substituting values: if (3 > 2 and 3 > 4) → false
- If the condition is false, move to the next iteration.
- Iteration 3 (i = 3):
- Condition: if (arr[i] > arr[i-1] and arr[i] > arr[i+1])
- Evaluates to: if (arr[3] > arr[2] and arr[3] > arr[4])
- Substituting values: if (4 > 3 and 4 > 3) → true
- The condition is true, so the code returns i, which is 3.
Output:
The function returns 3 as the index of the peak element in the array.
Steps to write code
Step 1: Initialize Variables:
- Calculate the size of the array n using arr.size().
Step 2: Check First and Last Elements:
- Check if the first element is greater than the second element.
- If true, return the index 0.
- Check if the last element is greater than the second-to-last element.
- If true, return the index n-1.
Step 3: Iterate Through the Array:
- Use a for loop to iterate through the array from index 1 to n-2.
- For each index i, check if the element at index i is greater than both its previous (i-1) and next (i+1) elements.
- If true, return the index i.
Step 4: Return -1 If No Peak Found:
- If no peak element is found during the iteration, return -1 (though theoretically, there should always be a peak element in a non-empty array).
Brute Force in All Languages
Peak index in a mountain array solution C++
class Solution {
public:
// Function to find the peak index in a mountain array
int peakIndexInMountainArray(vector<int>& arr) {
int n = arr.size();
// Check if the first element is the peak
if(arr[0] > arr[1]) return 0;
// Check if the last element is the peak
if(arr[n-1] > arr[n-2]) return n-1;
// Iterate through the array to find the peak element
for(int i=1; i<n-1; ++i) {
// If the current element is greater than its neighbors, it is the peak
if(arr[i] > arr[i-1] && arr[i] > arr[i+1]) {
return i;
}
}
// Return -1 if no peak is found
return -1;
}
};Peak index in a mountain array solution java
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
// Check if the first element is the peak
if(arr[0] > arr[1]) return 0;
// Check if the last element is the peak
if(arr[n-1] > arr[n-2]) return n-1;
// Iterate through the array to find the peak element
for(int i = 1; i < n - 1; ++i) {
// If the current element is greater than its neighbors, it is the peak
if(arr[i] > arr[i-1] && arr[i] > arr[i+1]) {
return i;
}
}
// Return -1 if no peak is found
return -1;
}
}Peak index in a mountain array solution python
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
n = len(arr)
# Check if the first element is the peak
if arr[0] > arr[1]:
return 0
# Check if the last element is the peak
if arr[n-1] > arr[n-2]:
return n-1
# Iterate through the array to find the peak element
for i in range(1, n-1):
# If the current element is greater than its neighbors, it is the peak
if arr[i] > arr[i-1] and arr[i] > arr[i+1]:
return i
# Return -1 if no peak is found
return -1Peak index in a mountain array solution javascript
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function(arr) {
const n = arr.length;
// Check if the first element is the peak
if (arr[0] > arr[1]) return 0;
// Check if the last element is the peak
if (arr[n - 1] > arr[n - 2]) return n - 1;
// Iterate through the array to find the peak element
for (let i = 1; i < n - 1; i++) {
// If the current element is greater than its neighbors, it is the peak
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
return i;
}
}
// Return -1 if no peak is found
return -1;
};Complexity Analysis of Peak Index in a Mountain Array leetcode Solution
Time Complexity: O(n)
Initialization:
- The variable n is initialized with the size of the array using arr.size().
- Time complexity: O(1) (constant time).
Checking First and Last Elements:
- The code checks if the first element is greater than the second element.
- Similarly, the code checks if the last element is greater than the second-to-last element.
- Time complexity for each of these checks: O(1) (constant time).
Iterating Through the Array:
- The for loop iterates from index 1 to n-2.
- For each iteration, the code performs a comparison to check if the element at index i is greater than both its previous (i-1) and next (i+1) elements
- Total time complexity for the loop: O(n-2) * O(1) = O(n-2).
- Since we consider the dominant term in Big-O notation, O(n-2) is equivalent to O(n).
Returning -1:
- If no peak element is found in the array, the code returns -1.
- Time complexity: O(1) (constant time).
Hence total time complexity of the code is O(n)
Space Complexity: O(n)
Auxiliary Space Complexity:
- Definition: The extra space or temporary space used by the algorithm during its execution, excluding the input data.
- Code Analysis: The given code uses a few variables:
- n for storing the size of the array.
- Loop variable i for iteration.
- All these variables take constant space.
- Auxiliary Space Complexity: O(1).
Total Space Complexity:
The overall space used by the algorithm, including the input data and auxiliary space.
- Input Data: The input array arr requires space proportional to its size.
- If n is the number of elements in the array, the space required is O(n).
- Auxiliary Space: As determined above, the auxiliary space is O(1).
- Total Space Complexity: Combining the space used by the input data and the auxiliary space:
Hence total space Complexity is O(n) + O(1) = O(n)
Is the brute force approach efficient?
The time complexity of the brute force approach goes up to O(n). A system can do at most 106 operations in a second. In the problem n goes up to 105. Hence O(n) is sufficient enough to pass all the testcases with ease.
But as per the problem statement. We need write a solution with O(log n) complexity. Now let's try to reduce our complexity from O(n) to O(log n).
To do so we will make use of some critical observations and figure out how we can do this.
Optimal Approach
Intuition:
From the brute force approach, we know that our array has two parts.
- 0 to peak index (here slope is positive,, meaning values are increasing)
- peak index to n-1 (here slope is negativ,negative meaning values are decreasing)
To optimize our peak index in a mountain array leetcode solution, we can't afford to traverse through every position in the array. Instead, we need to strategically select a part of the array where we are confident that we can find the peak. In this problem, a peak is defined as a value that is greater than its neighbours (left and right).
Let's imagine we picked some random index i from the array given to us. This index i can either be the peak index or not. If it's not the peak index, then it will either be on the left side of the peak (part of the positive slope) or on the right side of the peak (part of the negative slope).
Case 1: Index i on the left of the Peak
Suppose our chosen index i is on the left of the peak index. This indicates that all values to the right, up to the peak, are greater than the value at index i. Since the array ascends towards the peak, we can confidently deduce that the peak lies to the right of index i. Therefore, we should focus our search on the right side of the array.
Example:
- Array: [1, 3, 8, 12, 4, 2]
- Chosen Index i: 2 (Value: 8)
- Peak Index: 3 (Value: 12)
Since the value at index 2 (which is 8) is less than the value at index 3 (which is 12), and the array ascends towards the peak, we can confidently deduce that the peak lies to the right of index 2. Therefore, we should focus our search on the right side of the array (indices 3 to 5).
Case 2: Index i on the right of the Peak
Now, let's assume our chosen index i is to the right of the peak index. This indicates that all values to the left, up to the peak, are greater than the value at index i. Since the array descends after the peak, we can confidently conclude that the peak lies to the left of index i. Therefore, we should focus our search on the left side of the array.
Example:
- Array: [1, 3, 8, 12, 4, 2]
- Chosen Index i: 5 (Value: 4)
- Peak Index: 3 (Value: 12)
Since the value at index 4 (which is 4) is less than the value at index 3 (which is 12), and the array descends after the peak, we can confidently conclude that the peak lies to the left of index 4. Therefore, we should focus our search on the left side of the array (indices 0 to 3).
By using this approach, we avoid the need to examine every index to check for the peak condition. This allows us to narrow down our search space and make an informed decision about whether the peak lies to the left or right of the chosen index.
Peak index in a mountain array Algorithm
We start by defining our search space by defining two pointers, one at index 0 and the other at n-1. This means that initially, the whole array is the search space then we choose our arbitrary index within the search space. For efficiency, this index lies at the middle of the search space.
Based on the comparison, we then decide whether to search the right or left side of the array. This way, we can completely disregard the other half, thereby improving the time complexity. This method is known as binary search.
To know more about binary search. Refer to the article given below.
By continuously applying a binary search algorithm and progressively narrowing down our search space, we will eventually find the peak index. This systematic approach ensures that we focus on the most promising section of the array, leading us directly to the peak.
Optimal animation for Peak Index in a Mountain Array
Peak index in a mountain array solution example
Input: arr = [1, 2, 3, 4, 3, 1]
Output: 3
Explanation: All the elements to the left and right of index 3 (value = 4) are smaller hence 3 is the peak.
Initial State:
- arr = [1, 2, 3, 4, 3, 1]
- start = 0
- end = arr.size() - 1 = 5
- First Iteration:
- Calculate mid: mid = (start + end) / 2 = (0 + 5) / 2 = 2
- Compare arr[mid] with arr[mid + 1]: arr[2] > arr[3] -- 3 > 4 -- false
- Since the condition arr[mid] > arr[mid + 1] is false, update start: start = mid + 1 = 2 + 1 = 3
- State after iteration 1:
- start = 3
- end = 5
- Second Iteration:
- Calculate mid: mid = (start + end) / 2 = (3 + 5) / 2 = 4
- Compare arr[mid] with arr[mid + 1]: arr[4] > arr[5] -- 3>1 -- true
- Since the condition arr[mid] > arr[mid + 1] is true, update end: end = mid = 4
- State after iteration 2:
- start = 3
- end = 4
- Third Iteration:
- Calculate mid: mid = (start + end) / 2 = (3 + 4) / 2 = 3
- Compare arr[mid] with arr[mid + 1]: arr[3] > arr[4] -- 4 > 3 -- true
- Since the condition arr[mid] > arr[mid + 1] is true, update end: end = mid = 3
- State after iteration 3:
- start = 3
- end = 3
The while loop condition start < end is no longer true (since start = end = 3), so the loop terminates.
Return start: (start = 3)
Steps to write code
Step 1: Initialize Variables:
- Define two pointers: start (initialize to 0) and end (initialize to arr.size() - 1).
Step 2: Implement Binary Search Loop:
- Use a while loop that continues as long as start < end.
Step 3: Calculate the Middle Index:
- Inside the loop, calculate the middle index mid using the formula (start + end) / 2.
Step 4: Compare Middle Element with the Next Element:
- Compare the middle element arr[mid] with the next element arr[mid + 1].
Step 5: Adjust Search Space Based on Comparison:
- If arr[mid] > arr[mid + 1], it means you are in the descending part of the mountain array. Update end to mid.
- Otherwise, you are in the ascending part of the mountain array. Update start to mid + 1.
Step 6: Return the Peak Index:
- When the while loop terminates (i.e., start == end), the start pointer will be pointing to the peak index. Return start.
Optimal Approach in All Languages
Peak index in a mountain array solution C++
class Solution {
public:
// Function to find the peak index in a mountain array
int peakIndexInMountainArray(vector<int>& arr) {
// Initialize start and end pointers
int start = 0, end = arr.size() - 1;
// Continue searching while start is less than end
while (start < end) {
// Calculate the middle index
int mid = (start + end) / 2;
// If the middle element is greater than the next element
if (arr[mid] > arr[mid + 1]) {
// Move the end pointer to the middle
end = mid;
} else {
// Move the start pointer to the middle + 1
start = mid + 1;
}
}
// Return the peak index
return start;
}
};Peak index in a mountain array solution java
class Solution {
// Function to find the peak index in a mountain array
public int peakIndexInMountainArray(int[] arr) {
// Initialize start and end pointers
int start = 0, end = arr.length - 1;
// Continue searching while start is less than end
while (start < end) {
// Calculate the middle index
int mid = (start + end) / 2;
// If the middle element is greater than the next element
if (arr[mid] > arr[mid + 1]) {
// Move the end pointer to the middle
end = mid;
} else {
// Move the start pointer to the middle + 1
start = mid + 1;
}
}
// Return the peak index
return start;
}
}Peak index in a mountain array solution python
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
# Initialize start and end pointers
start, end = 0, len(arr) - 1
# Continue searching while start is less than end
while start < end:
# Calculate the middle index
mid = (start + end) // 2
# If the middle element is greater than the next element
if arr[mid] > arr[mid + 1]:
# Move the end pointer to the middle
end = mid
else:
# Move the start pointer to the middle + 1
start = mid + 1
# Return the peak index
return startPeak index in a mountain array solution javascript
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function(arr) {
// Initialize start and end pointers
let start = 0, end = arr.length - 1;
// Continue searching while start is less than end
while (start < end) {
// Calculate the middle index
let mid = Math.floor((start + end) / 2);
// If the middle element is greater than the next element
if (arr[mid] > arr[mid + 1]) {
// Move the end pointer to the middle
end = mid;
} else {
// Move the start pointer to the middle + 1
start = mid + 1;
}
}
// Return the peak index
return start;
};Complexity Analysis of peak index in a mountain array Solution
Time Complexity: O(logn)
Initialization:
- Initializing the variables start and end takes constant time O(1).
Binary Search Loop:
- The while loop runs as long as start < end.
- In each iteration of the loop, the search space is halved by updating either start or end.
n --> n/2 --> n/4 --> n/8 --> n/16 -->.... 1 - This halving process is similar to the binary search algorithm, which operates in logarithmic time.
- Therefore, the time complexity of the loop is O(log n), where n is the number of elements in the array.
Return Statement:
- Returning the value of start takes constant time O(1).
Hence, Overall Time Complexity of the code is: O(logn)
Space Complexity: O(1)
Auxiliary Space Complexity:
The extra space or temporary space used by the algorithm during its execution, excluding the input data.
- Code Analysis: The given code uses a few variables:
- start and end for defining the search range.
- mid for storing the middle index during the binary search iterations.
- All these variables take constant space.
Auxiliary Space Complexity: O(1).
Total Space Complexity:
The overall space used by the algorithm, including the input data and auxiliary space
- Input Data: The input array arr requires space proportional to its size. which is n. Hence the space required is O(n).
- Auxiliary Space: As determined above, the auxiliary space is O(1).
Total Space Complexity: O(n) + O(1) = O(n).
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems:-
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
(This problem is an interactive problem.)
You may recall that an array arr is a mountain array if and only if:
- arr.length >= 3
- There exists some i with 0 < i < arr.length - 1 such that:
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index does not exist, return -1.
You cannot access the mountain array directly. You may only access the array using a MountainArray interface:
- MountainArray.get(k) returns the element of the array at index k (0-indexed).
- MountainArray.length() returns the length of the array.
Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.
FAQ
What is the peak index of a mountain array?
A peak index in a mountain array is the position of the highest value, where numbers first rise and then fall. It's significant for understanding the array's structure. To find it, compare middle elements in a binary search-like method, narrowing down until the highest point is identified. Simple, quick, and efficient!