Find Peak Element
Mahabharata — Any Local Summit — Finding Any Warrior Taller Than Both Neighbors
न केवलं शिखरम् — यस्य दोनों पार्श्वौ न्यूनः। सः अपि शिखरः — तं खोजो द्रुततया॥
*Not only the highest summit — any point taller than both neighbors is a peak. Find it swiftly.*
The Story
Find ANY element that is strictly greater than its neighbors. The array may have multiple peaks; return any one.
For `nums = [1,2,3,1]`: peak at index 2 (value 3). For `nums = [1,2,1,3,5,6,4]`: peaks at index 1 or 5 — return either.
Unlike bs-6 (guaranteed single mountain), here multiple local peaks may exist. We need to find any one.
**Same binary search approach — slope direction:** If `nums[mid] < nums[mid+1]`: mid is on an ascending slope → there MUST be a peak to the right (since the array eventually ends, which means it must come back down) If `nums[mid] >= nums[mid+1]`: mid is on a descending slope or is a peak → there MUST be a peak at mid or to the left
```java int left=0, right=n-1; while (left < right) { int mid = left + (right-left)/2; if (nums[mid] < nums[mid+1]) left = mid+1; else right = mid; } return left; ```
This is IDENTICAL to bs-6's code! The difference is just the guarantee — in bs-7, any peak works.
**Why it's correct for multiple peaks:** At each step, we maintain the invariant that a peak exists in [left, right]. When ascending, any peak in the right half qualifies. When descending/at-peak, any peak in the left half (including mid) qualifies.
The Neighbor-Check Scanner
Check each element against its neighbors. Return first index where arr[i] > arr[i-1] and arr[i] > arr[i+1]. O(n).
public int findPeakElementBruteForce(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
boolean leftOk = (i==0) || nums[i] > nums[i-1];
boolean rightOk = (i==n-1) || nums[i] > nums[i+1];
if (leftOk && rightOk) return i;
}
return -1;
}The Slope-Direction Peak Wisdom
public int findPeakElement(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; // Ascending: peak must be right
} else {
right = mid; // Descending/peak: peak is mid or left
}
}
return left;
}Step-by-Step Walkthrough
[1,2] — peak at index 1 l=0,r=1,mid=0,nums[0]=1<nums[1]=2 → l=1 l==r=1 → return 1 ✅
Deep Insight
**bs-6 vs bs-7 code:** IDENTICAL. The difference is conceptual: bs-6 guarantees one global peak (mountain), bs-7 finds any local peak.
**Why the invariant holds:** We always maintain that [left, right] contains at least one peak: - Base: left=0, right=n-1 contains a peak (guaranteed by problem) - If ascending at mid: right half must contain a peak (the value keeps increasing, so it must eventually decrease → peak exists right of mid) - If descending/flat at mid: left half including mid must contain a peak
**Edge cases:** Single element → left==right from the start → return left. Two elements → find the larger one in one step.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Check each element's neighbors |
| Optimal | O(log n) | O(1) | Binary search on slope direction |
Pattern Recognition
✅ Find any local peak (greater than both neighbors) ✅ Same code as bs-6 (mountain peak) ✅ Invariant: peak always exists in [left,right] ✅ Ascending→go right; else→go left (include mid) **LeetCode Trigger Phrases:** → "find peak element" → "any element greater than its neighbors" → O(log n) peak finding
Bhagavad Gita 13.11
अध्यात्मज्ञाननित्यत्वं तत्त्वज्ञानार्थदर्शनम्। एतज्ज्ञानमिति प्रोक्तमज्ञानं यदतोऽन्यथा॥
Constant knowledge of the Self, perception of the goal of true knowledge — all this is declared to be knowledge; all that is contrary to this is ignorance.
Connection: Any local peak — not just the global maximum — is a valid answer. This mirrors the Gita's teaching that wisdom can be found at many points, not just the supreme summit. Each local peak represents a point of local clarity and elevation. The binary search finds one such point of clear ascendance over its neighbors — a valid vantage point — without needing to scan every position in the landscape.