Peak Element Finder in Mountain Array — Problem Statement & Solution Guide
Problem Description
Given an array nums that first strictly increases then strictly decreases (a mountain array), locate the index of the maximum element (the peak). The peak is the only element that is greater than both its immediate neighbours. Return the index of this element. It is guaranteed that such a peak exists and the array length is at least three.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Peak Element Finder in Mountain Array"
WHY DOES IT MATTER?
This pattern is essential because it demonstrates how to leverage structural properties (monotonicity) to reduce search complexity. It is a foundational technique for problems involving unimodal functions, such as finding the minimum in a rotated sorted array or locating the inflection point in optimization algorithms. Mastering this pattern enhances one's ability to recognize when binary search can be applied beyond simple sorted arrays.
OPTIMIZATION CHALLENGE
The key insight is that the comparison nums[mid] < nums[mid + 1] provides directional information about the location of the peak. This allows the search space to be halved in each step, transforming an O(n) linear scan into an O(log n) logarithmic search. The challenge lies in correctly handling the boundary conditions to ensure the search does not miss the peak at the edges of the search space.
REAL-WORLD CONNECTION
In distributed systems, this pattern is analogous to finding the 'hotspot' in a load-balanced cluster. If server load metrics form a mountain array (increasing load up to a peak server, then decreasing), binary search can quickly identify the overloaded server without polling all nodes. This is critical in auto-scaling decisions where rapid identification of bottlenecks prevents system-wide degradation.
During the interview, explicitly state that you are using binary search on the 'slope' rather than the 'value'. Emphasize that the peak is the point where the slope changes from positive to negative. This framing shows a deeper understanding of the algorithm's mechanics and helps in adapting the solution to variations (e.g., finding the minimum in a valley array).
COMPLEXITY AT A GLANCE
O(log n)O(1)Core Theory — Why This Approach?
The problem of finding a peak in a mountain array is a classic application of binary search, specifically leveraging the monotonic properties of the sub-arrays. A mountain array is defined by two distinct phases: a strictly increasing sequence followed by a strictly decreasing sequence. This structure implies that for any index mid, if nums[mid] < nums[mid + 1], the peak must lie to the right of mid because the array is still ascending. Conversely, if nums[mid] > nums[mid + 1], the peak must be at mid or to the left, as the array has started descending. This property allows us to discard half of the search space in each iteration, reducing the problem from a linear scan to a logarithmic search.
Naive approaches, such as iterating through the entire array to find the maximum element, operate in O(n) time complexity. While acceptable for small datasets, this linear time complexity becomes a bottleneck in high-frequency trading systems or real-time data processing pipelines where latency is critical. The optimal paradigm here is not just 'finding the maximum' but 'locating the inflection point' of a unimodal function. By recognizing that the array represents a discrete unimodal function, we can apply divide-and-conquer strategies that exploit the local slope information to guide the global search.
The theoretical underpinning relies on the fact that the peak is the unique point where the derivative (difference between adjacent elements) changes sign from positive to negative. In discrete terms, we are looking for the index i where nums[i-1] < nums[i] and nums[i] > nums[i+1]. Binary search adapts to this by treating the comparison nums[mid] < nums[mid+1] as a decision rule: if true, the 'slope' is positive, so we move right; if false, the 'slope' is non-positive, so we move left. This ensures convergence to the peak in O(log n) time, which is asymptotically optimal for comparison-based searches in sorted-like structures.
Interview Questions on This Problem
Q1At a fintech platform processing high-frequency trade data, you need to identify the peak latency spike in a time-series array. How would you adapt the mountain array peak finder if the data contains noise (i.e., not strictly increasing/decreasing)?
In a noisy environment, the strict monotonicity assumption breaks. A robust approach would involve smoothing the data first (e.g., using a moving average) to approximate the mountain shape, or using a modified binary search that tolerates small deviations. Alternatively, if the noise is bounded, one could use a ternary search variant or a local maximum finder that checks a window of neighbors. However, for interview purposes, emphasize that the core binary search logic remains valid if the 'mountain' structure is preserved on a macro scale, and discuss how to handle edge cases where nums[mid] == nums[mid+1] by adjusting the search boundaries conservatively.
Q2You are designing a distributed system where multiple nodes hold segments of a large mountain array. How would you coordinate to find the global peak efficiently without transferring the entire array?
This requires a distributed binary search strategy. Each node can perform a local binary search on its segment to determine if the peak lies within its range or if the peak is at the boundary. By exchanging boundary values (the max of the left segment and the max of the right segment), the coordinator can determine which segment contains the global peak. This reduces communication overhead to O(log n) messages, each of constant size, rather than O(n) data transfer. The key is to ensure that the boundary checks correctly identify the 'slope' direction at the segment edges to guide the next search phase.
Q3In a high-growth startup's recommendation engine, user preference scores form a mountain array. How would you optimize the peak finder if the array is updated frequently (dynamic mountain array)?
For dynamic updates, a static binary search is insufficient. One could use a segment tree or a binary indexed tree (Fenwick tree) that supports range maximum queries and point updates in O(log n) time. The peak can then be found by querying the maximum value and its index. Alternatively, if updates are localized, a lazy propagation segment tree can maintain the mountain property and allow efficient peak detection. The trade-off is higher space complexity (O(n)) for faster query times, which is often acceptable in recommendation systems where query latency is more critical than memory footprint.
Examples
Input
[2,5,9,12,8,3]
Output
3
Explanation: The sequence rises from 2 to 12 and then falls. The element 12 at index 3 is larger than its neighbours 9 and 8, so the answer is 3.
Input
[1,4,7,10,9,6,2]
Output
3
Explanation: Values increase up to 10 at index 3, then decrease. 10 > 7 and 10 > 9, thus index 3 is returned.
Input
[0,3,5,7,6,4,1]
Output
3
Explanation: The peak 7 occurs at index 3, being greater than 5 on the left and 6 on the right.
Constraints
- 3 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums[0] < nums[1]
- nums[nums.length-2] > nums[nums.length-1]
Optimal Approach & Strategy
Use binary search to find the peak. Initialize left and right pointers to the start and end of the array. While left is less than right, calculate the middle index. If nums[mid] is less than nums[mid + 1], move left to mid + 1; otherwise, move right to mid. Return left when the loop ends.
Brute Force Approach
Iterate through the entire array from left to right, keeping track of the maximum element and its index. Return the index of the maximum element found.
Verified Code Solutions
function findPeak(nums) {
let left = 0, right = nums.length - 1;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] < nums[mid + 1]) {
left = mid + 1; // peak is to the right
} else {
right = mid; // peak is at mid or left side
}
}
return left; // left == right
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if (data.length===0) process.exit(0);
const n = data[0];
const nums = data.slice(1,1+n);
console.log(findPeak(nums));#include <bits/stdc++.h>
using namespace std;
int findPeak(const vector<int>& nums) {
int left = 0, right = (int)nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1])
left = mid + 1; // peak is to the right
else
right = mid; // peak is at mid or to the left
}
return left; // left == right == peak index
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> nums(n);
for(int i=0;i<n;++i) cin>>nums[i];
cout<<findPeak(nums);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static int findPeak(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1]) {
left = mid + 1; // peak is to the right
} else {
right = mid; // peak is at mid or left side
}
}
return left; // left == right
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
List<Integer> list = new ArrayList<>();
String line;
while ((line = br.readLine()) != null) {
line = line.trim();
if (line.isEmpty()) continue;
for (String s : line.split("\\s+")) {
list.add(Integer.parseInt(s));
}
}
if (list.isEmpty()) return;
int n = list.get(0);
int[] nums = new int[n];
for (int i = 0; i < n; i++) nums[i] = list.get(i + 1);
System.out.print(findPeak(nums));
}
}def find_peak(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1 # peak is to the right
else:
right = mid # peak is at mid or to the left
return left
if __name__ == "__main__":
import sys
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
sys.exit()
n = data[0]
nums = data[1:1+n]
print(find_peak(nums))function findPeak(nums) {
let left = 0, right = nums.length - 1;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] < nums[mid + 1]) {
left = mid + 1; // peak is to the right
} else {
right = mid; // peak is at mid or left side
}
}
return left; // left == right
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if (data.length===0) process.exit(0);
const n = data[0];
const nums = data.slice(1,1+n);
console.log(findPeak(nums));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.