Find Peak Element

Difficulty: Medium
Topics: Array, Binary Search
Link: https://leetcode.com/problems/find-peak-element/

Problem Description

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.

Example 1:


Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:


Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
nums[i] != nums[i + 1] for all valid i.

Solution

1. Problem Deconstruction

Technical Restatement
Given a 0-indexed integer array nums of length n, find any index i ∈ [0, n-1] such that:

For 0 < i < n-1: nums[i] > nums[i-1] and nums[i] > nums[i+1]
For i = 0: nums[i] > nums[i+1] (since nums[-1] = -∞)
For i = n-1: nums[i] > nums[i-1] (since nums[n] = -∞)

The algorithm must run in O(log n) time, implying a binary search or divide-and-conquer strategy. The constraint nums[i] != nums[i+1] ensures strictly increasing/decreasing adjacent pairs, guaranteeing at least one peak exists and enabling slope-based decisions.

Beginner-Friendly Restatement
Imagine you have a list of numbers. A “peak” is a number that is bigger than the numbers right next to it. The first number only has a neighbor to its right; it’s a peak if it’s bigger than that neighbor. The last number only has a neighbor to its left; it’s a peak if it’s bigger than that neighbor. We want to find the position (index) of any such peak. We need to do this quickly, without checking every number one by one.

Mathematical Formulation
Let A = [a₀, a₁, ..., aₙ₋₁] be an array of integers with aᵢ ≠ aᵢ₊₁ for all 0 ≤ i < n-1. Define virtual boundaries a₋₁ = aₙ = -∞. Find any index k satisfying:
aₖ > aₖ₋₁ and aₖ > aₖ₊₁
where comparisons with virtual indices automatically hold due to -∞. Equivalently, find a local maximum of the discrete function f(i) = aᵢ.

Constraint Analysis

1 <= nums.length <= 1000
- Limits input size but does not relax O(log n) requirement. A linear scan would be acceptable in practice, but the problem demands logarithmic time.
- Small n means even suboptimal algorithms run fast, but we must adhere to the stated complexity.
-2³¹ <= nums[i] <= 2³¹ - 1
- Values fit 32-bit signed integers. No overflow concerns during comparisons.
- Negative numbers are allowed, so peaks can be negative (e.g., [-5, -2, -3] has peak -2 at index 1).
nums[i] != nums[i + 1] for all valid i
- Critical for binary search: Ensures every adjacent pair is strictly increasing or decreasing.
- Guarantees existence of at least one peak (by the Extreme Value Theorem for discrete functions).
- Eliminates plateaus, simplifying slope analysis.

Hidden Edge Cases

n = 1: The single element is trivially a peak.
n = 2: The larger element is a peak (e.g., [1,2] → index 1; [2,1] → index 0).
Strictly increasing array: Last element is a peak.
Strictly decreasing array: First element is a peak.
Alternating sequences (e.g., [1,3,2,4,1]) contain multiple peaks.

2. Intuition Scaffolding

Real-World Metaphor
Imagine hiking on a mountain range at night with only a flashlight. You want to reach any peak. At your current spot, you check the slope: if the ground rises to your right, you go right because a peak likely lies that way. If it falls, you go left. By repeatedly halving your search range this way, you efficiently find a peak without traversing every hill.

Gaming Analogy
In a terrain-generation game, you need to place a flag at the highest local point. The map is a 1D heightmap. Instead of scanning the entire map, you use a “probe” at the midpoint: if heights increase to the east, discard the western half; otherwise, discard the eastern half. Repeat until the probe sits on a peak.

Math Analogy
Consider a discrete function f: ℤ → ℝ with f(i) ≠ f(i+1). By the intermediate value property (adapted for discrete differences), if f(mid) < f(mid+1), then there exists an index j > mid where f(j) > f(j+1) (since f(n) is effectively -∞). Thus, a peak must exist in [mid+1, right]. The symmetric argument applies when f(mid) > f(mid+1).

Common Pitfalls

Returning Global Maximum
- Why it’s tempting: A global max is always a peak.
- Why it fails: Requires O(n) time, violating O(log n) constraint.
Assuming Sorted Array for Binary Search
- Why it’s tempting: Binary search typically works on sorted data.
- Why it’s wrong: The array is unsorted, but we can still discard half based on local slope.
Ignoring Edge Indices
- Example: In [1,2], index 0 is not a peak because 1 < 2.
- Fix: Treat virtual boundaries as -∞.
Checking Both Neighbors Unnecessarily
- Why it’s inefficient: Binary search only needs comparison with one neighbor to decide direction.
Infinite Loop in Binary Search
- Scenario: Incorrectly updating left = mid instead of mid + 1 when slope increases.
- Result: Loop stagnates when mid equals left.
Overlooking Strict Inequality Constraint
- If nums[i] == nums[i+1] were allowed, binary search would fail at flat regions.

3. Approach Encyclopedia

Approach 1: Linear Scan (Brute Force)

Idea: Check every index to see if it’s a peak.

Pseudocode:

for i from 0 to n-1:
    left = nums[i-1] if i > 0 else -∞
    right = nums[i+1] if i < n-1 else -∞
    if nums[i] > left and nums[i] > right:
        return i

Complexity Proof:
- Time: O(n) – one loop with constant work per iteration.
- Space: O(1) – only a few variables.

Visualization:

nums = [1, 2, 3, 1]
i=0: left=-∞, right=2 → 1>2? ✗
i=1: left=1, right=3 → 2>1? ✓, 2>3? ✗
i=2: left=2, right=1 → 3>2? ✓, 3>1? ✓ → PEAK at index 2

Approach 2: Binary Search (Optimal)

Idea: Use binary search on indices. At each step, compare nums[mid] with nums[mid+1] to decide which half must contain a peak.
Invariant: A peak exists within [left, right].
Proof of Correctness:
- If nums[mid] < nums[mid+1], then:
  - mid cannot be a peak (since right neighbor is larger).
  - The sequence increases at mid, and because nums[n] = -∞, there must be a decrease somewhere to the right ⇒ a peak exists in [mid+1, right].
- If nums[mid] > nums[mid+1], then:
  - mid could be a peak (if also > left neighbor), or a peak exists to the left because the sequence decreases at mid and eventually must increase (since nums[-1] = -∞) ⇒ a peak exists in [left, mid].

Pseudocode:

left = 0, right = n-1
while left < right:
    mid = (left + right) // 2
    if nums[mid] < nums[mid+1]:
        left = mid + 1   # Peak in right half
    else:
        right = mid      # Peak in left half (including mid)
return left

Complexity Proof:
- Time: O(log n) – each iteration halves the search space.
  - Recurrence: T(n) = T(n/2) + O(1) ⇒ T(n) = O(log n) by Master Theorem.
- Space: O(1) – iterative, constant extra memory.

Visualization:

nums = [1, 2, 1, 3, 5, 6, 4], n=7
Initial: left=0, right=6
Iter1: mid=3, nums[3]=3 < nums[4]=5 → left=4
Iter2: mid=5, nums[5]=6 > nums[6]=4 → right=5
Iter3: mid=4, nums[4]=5 < nums[5]=6 → left=5
Now left=right=5 → return 5 (peak at index 5)

Approach 3: Recursive Divide & Conquer

Idea: Recursively check mid and narrow to the half with a higher neighbor.

Pseudocode:

function search(nums, left, right):
    if left == right:
        return left
    mid = (left + right) // 2
    if nums[mid] < nums[mid+1]:
        return search(nums, mid+1, right)
    else:
        return search(nums, left, mid)

Complexity:
- Time: O(log n) – same recurrence as iterative binary search.
- Space: O(log n) – recursion call stack depth.

4. Code Deep Dive

def findPeakElement(nums):
    """
    Finds a peak element index using iterative binary search.
    Args:
        nums: List[int], length >= 1, with nums[i] != nums[i+1]
    Returns:
        int: index of a peak element
    """
    left, right = 0, len(nums) - 1   # 1. Initialize search space
    
    while left < right:               # 2. Loop until search space collapses
        mid = (left + right) // 2     # 3. Midpoint (floor division)
        
        # 4. Compare with right neighbor (key decision)
        if nums[mid] < nums[mid + 1]:
            left = mid + 1            # 5. Discard left half
        else:
            right = mid               # 6. Discard right half (keep mid)
    
    return left                       # 7. Peak index found

Line-by-Line Annotation

left, right = 0, len(nums) - 1
- Sets initial search interval to the entire array.
- Why?: The peak is guaranteed to exist within [0, n-1].
while left < right:
- Continues until left and right converge to a single index.
- Why < not <=?: When left == right, we’ve found the peak.
mid = (left + right) // 2
- Computes midpoint. Integer division ensures valid index.
- Why floor?: Prevents overflow and works for even/odd lengths.
if nums[mid] < nums[mid + 1]:
- Compares current element with its right neighbor.
- Why only right neighbor?: The strict inequality constraint ensures we can decide direction.
- What about left neighbor?: Unnecessary; the invariant guarantees a peak on the side with higher slope.
left = mid + 1
- If slope is increasing, the peak must be to the right (mid cannot be a peak).
- Why mid + 1?: We safely discard mid because it’s smaller than mid+1.
right = mid
- If slope is decreasing, the peak is at mid or to the left.
- Why not mid - 1?: mid could be the peak (if > left neighbor), so we keep it.
return left
- When loop ends, left == right and points to a peak.
- Proof: The invariant ensures the remaining index satisfies peak conditions.

Edge Case Handling

Single element (n=1): Loop skipped, returns 0.
Two elements (n=2):
- [1,2]: mid=0, 1<2 → left=1 → return 1.
- [2,1]: mid=0, 2>1 → right=0 → return 0.
Strictly increasing: Last index returned (e.g., [1,2,3,4] → 3).
Strictly decreasing: First index returned (e.g., [4,3,2,1] → 0).
Multiple peaks: Returns one valid peak (depends on array layout).

5. Complexity War Room

Hardware-Aware Analysis

Time: O(log n) iterations. For n=1000, ~10 iterations → < 1 µs on modern CPUs.
Space: O(1) → uses ~24 bytes (three integers), fits in CPU registers.
Cache Efficiency: Sequential array accesses (nums[mid], nums[mid+1]) exhibit good locality; likely in L1 cache.

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Linear Scan	O(n)	O(1)	10/10	❌ Fails O(log n) requirement
Binary Search (Iterative)	O(log n)	O(1)	8/10	✅ Optimal, expected
Binary Search (Recursive)	O(log n)	O(log n)	7/10	⚠️ Acceptable but overhead
Global Maximum	O(n)	O(1)	9/10	❌ Not O(log n)

Why Binary Search Wins

Meets O(log n) requirement.
Minimal memory footprint.
Elegant invariant: “A peak exists in [left, right]”.
Works for all edge cases.

6. Pro Mode Extras

Variants & Extensions

Find Valley Element
- Change comparisons: if nums[mid] > nums[mid+1], go right; else go left.
- Virtual boundaries become +∞.
Find All Peaks
- Requires O(n) scan.
- Collect indices where nums[i] > nums[i-1] and nums[i] > nums[i+1].
2D Peak Finding (LeetCode 1901)
- Matrix with m rows, n columns.
- Algorithm: Pick middle column, find global max in that column, compare with left/right neighbors, recurse. Complexity O(n log m).
Peak in Sorted & Rotated Array (LeetCode 33/153)
- Binary search comparing nums[mid] with nums[high] to decide direction.
Allow Adjacent Equalities
- If nums[i] == nums[i+1], binary search fails.
- Solution: Linear scan or modified binary search with three-way comparison (expand outward until inequality).

Interview Cheat Sheet

First Statement: “We can solve in O(log n) using binary search because the array has no adjacent equal elements.”
Key Insight: “Compare mid with its right neighbor to decide which half must contain a peak.”
Edge Cases: “Single element, two elements, strictly increasing/decreasing arrays.”
Invariant: “At each step, the current interval [left, right] contains at least one peak.”
Complexity: “Time O(log n), space O(1).”
Practice Question: “How would you modify this if we wanted the first peak?” (Answer: Still binary search, but direction may change.)

Final Optimization Notes

Use mid = left + (right - left) // 2 to avoid potential overflow (though not needed for n ≤ 1000).
In Python, while left < right is safe; in languages with zero-based loops, ensure right updates correctly.
The algorithm is deterministic for a given array: it always returns the same peak for the same input.

#162 - Find Peak Element

Find Peak Element

Problem Description

Solution

1. Problem Deconstruction

2. Intuition Scaffolding

3. Approach Encyclopedia

Approach 1: Linear Scan (Brute Force)

Approach 2: Binary Search (Optimal)

Approach 3: Recursive Divide & Conquer

4. Code Deep Dive

5. Complexity War Room

6. Pro Mode Extras