Peak Index in Mountain
Mahabharata — The Summit of Meru — Finding the Highest Point in the Sacred Mountain Array
पर्वतस्य शिखरं कुत्र? — चढ़ाई के पश्चात् उतराई। मध्ये खोजो — यत्र ऊर्ध्वगामी अधोगामी भवति॥
*Where is the mountain's peak? — After ascent comes descent. Search the middle — where upward becomes downward.*
The Story
A mountain array has elements that increase up to a peak, then decrease. Find the peak index.
For `arr = [0,2,1,0]`: peak at index 1 (value 2). Guaranteed: arr[0] < arr[1] < ... < arr[peak] > arr[peak+1] > ... > arr[n-1]
The key binary search insight: - If `arr[mid] < arr[mid+1]`: we're on the ASCENDING slope → peak is to the RIGHT (left=mid+1) - If `arr[mid] > arr[mid+1]`: we're on the DESCENDING slope → peak is to the LEFT or IS mid (right=mid)
Because we always land on a slope (never a flat), one comparison tells us which side the peak is on.
```java int left=0, right=arr.length-1; while (left < right) { int mid = left + (right-left)/2; if (arr[mid] < arr[mid+1]) left = mid+1; // ascending: peak right else right = mid; // descending: peak is mid or left } return left; // = right, the peak index ```
Trace `[0,1,0]`: - left=0, right=2, mid=1. arr[1]=1 > arr[2]=0 → right=1 - left=0, right=1, mid=0. arr[0]=0 < arr[1]=1 → left=1 - left==right=1 → return 1 ✓
**Critical insight:** We use `left < right` (not `<=`) and `right = mid` (not `mid-1`). This ensures we never skip the peak and the loop converges correctly.
**Why `right = mid` and not `right = mid-1`?** Because mid itself could be the peak — `arr[mid] > arr[mid+1]` means we're at or past the peak, and mid is a valid candidate.
The Linear Peak Finder
Scan for the first index where arr[i] > arr[i+1]. That's the peak. O(n).
public int peakIndexBruteForce(int[] arr) {
for (int i = 0; i < arr.length-1; i++)
if (arr[i] > arr[i+1]) return i;
return arr.length-1;
}The Slope-Direction Wisdom
public int peakIndexInMountainArray(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) {
left = mid + 1; // On ascending slope, peak is right
} else {
right = mid; // At or past peak, include mid
}
}
return left;
}Step-by-Step Walkthrough
[1,2,3,4,5,3,1] — peak at index 4 l=0,r=6,mid=3,arr[3]=4<arr[4]=5 → l=4 l=4,r=6,mid=5,arr[5]=3<arr[6]=1? No: arr[5]=3>arr[6]=1 → r=5 l=4,r=5,mid=4,arr[4]=5>arr[5]=3 → r=4 l==r=4 → return 4 ✅
Deep Insight
**bs-6 vs bs-7:** bs-6 guarantees a single mountain (one peak). bs-7 is more general — any local peak counts. The algorithm is nearly identical but bs-7 might have multiple candidates.
**Loop invariant:** At every step, the peak is in [left, right]. `left < right` ensures we continue until we've narrowed to a single element. `right = mid` (not `mid-1`) preserves the peak in the range.
**Why this works at all?** The mountain property guarantees exactly one peak. At any mid, either we're ascending (peak is right) or descending (peak is left/mid). This makes binary search work on a non-sorted array!
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Linear scan for slope change |
| Optimal | O(log n) | O(1) | Binary search on slope direction |
Pattern Recognition
✅ Mountain array — find peak index ✅ left<right loop; right=mid (not mid-1) ✅ arr[mid]<arr[mid+1]: ascending→left=mid+1 ✅ arr[mid]>arr[mid+1]: at/past peak→right=mid **LeetCode Trigger Phrases:** → "peak index in mountain array" → "find peak in bitonic array" → Binary search on non-sorted but structured array
Bhagavad Gita 10.23
मेरुः शिखरिणामहम्।
Among the peaked mountains, I am Meru.
Connection: Mount Meru — the cosmic axis, the supreme peak — is what the algorithm seeks. In the mountain array, there is one true summit: the point where ascending becomes descending. Binary search finds this peak not by climbing laboriously from the bottom but by reading the slope at each midpoint and discarding half the mountain with perfect confidence. This is wisdom: knowing which way the mountain goes from any point.