Find Peak Element

LeetCode 162: Find Peak Element Solution & Explanation

Problem Overview

TL;DR: By comparing the middle element with its immediate neighbor, we can determine the local slope of the array and eliminate the half that does not guarantee a peak, achieving logarithmic time complexity.

The LeetCode 162 problem, Find Peak Element, asks us to locate a "peak" in an array of integers. A peak is defined as an element strictly greater than its neighbors. The array is 0-indexed, and we are told to assume that elements outside the array boundaries are negative infinity ($-\infty$). Importantly, adjacent elements are guaranteed to be distinct. If multiple peaks exist, returning the index of any one of them is acceptable.

The critical requirement is that the solution must run in $O(\log n)$ time, suggesting that a linear scan is insufficient for an optimal interview solution.

Brute Force Approach for Find Peak Element

The most straightforward way to solve this problem is to iterate through the array and check every element's neighbors.

1. Iterate from index 0 to n-1.
2. For each index i, check if nums[i] > nums[i-1] (handling bounds) and nums[i] > nums[i+1] (handling bounds).
3. The first index satisfying this condition is returned.
4. Alternatively, finding the global maximum of the array via a linear scan also guarantees finding a peak, as the largest element is strictly greater than any existing neighbors.

Pseudocode:

for i from 0 to length - 1:
    is_peak = true
    if i > 0 and nums[i] < nums[i-1]:
        is_peak = false
    if i < length - 1 and nums[i] < nums[i+1]:
        is_peak = false
    if is_peak:
        return i

Time Complexity: $O(n)$. We may potentially visit every element in the array. Why it fails: While this approach produces the correct answer, the problem explicitly mandates an $O(\log n)$ time complexity. In a large-scale system or strict interview environment, an $O(n)$ solution is considered suboptimal when binary search is applicable.

Algorithm Strategy: Binary Search Patterns

We utilize the standard Binary Search template with a modification to the comparison logic.

1. Initialization: Set two pointers, left at 0 and right at n - 1.
2. Loop Condition: Continue while left < right. We stop when left meets right, effectively converging on a single index.
3. Midpoint Calculation: Calculate mid = left + (right - left) / 2.
4. Comparison: Check if nums[mid] < nums[mid + 1].
   • If true, we are on an upward slope. The peak lies to the right. We update left = mid + 1.
   • If false, we are on a downward slope (or mid is the peak). The peak lies to the left or is at mid. We update right = mid.
5. Result: When the loop terminates, left (and right) will point to a peak element. Return left.

Note: We compare mid with mid + 1. Because we use integer division, mid will always be less than right (as long as left < right), ensuring mid + 1 is a valid index within bounds.

Execution Flow

Consider the input: nums = [1, 2, 1, 3, 5, 6, 4]

1. Initial State:

   • left = 0, right = 6
   • mid = 0 + (6 - 0) / 2 = 3
   • nums[3] is 3.

2. Iteration 1:

   • Compare nums[mid] (3) vs nums[mid+1] (5).
   • 3 < 5 is True. We are on an ascending slope.
   • The peak must be to the right.
   • Update left = mid + 1 = 4.
   • Range is now indices [4, 6].

3. Iteration 2:

   • left = 4, right = 6.
   • mid = 4 + (6 - 4) / 2 = 5.
   • nums[5] is 6.
   • Compare nums[mid] (6) vs nums[mid+1] (4).
   • 6 < 4 is False. We are on a descending slope.
   • The peak is at mid or to the left.
   • Update right = mid = 5.
   • Range is now indices [4, 5].

4. Iteration 3:

   • left = 4, right = 5.
   • mid = 4 + (5 - 4) / 2 = 4.
   • nums[4] is 5.
   • Compare nums[mid] (5) vs nums[mid+1] (6).
   • 5 < 6 is True. Ascending slope.
   • Update left = mid + 1 = 5.
   • Range is now indices [5, 5].

5. Termination:

   • left (5) is not less than right (5). Loop ends.
   • Return left which is 5.
   • nums[5] = 6, which is a correct peak.

Proof of Correctness

The correctness relies on the invariant: The subarray nums[left...right] always contains at least one peak.

1. Base Case: The initial range [0, n-1] contains a peak. Since boundaries are $-\infty$, and the array is non-empty, there is at least one element larger than its neighbors (or the single element itself is the peak).
2. Inductive Step:
   • If nums[mid] < nums[mid+1], the slope is rising at mid. The subarray nums[mid+1...right] starts with nums[mid+1] > nums[mid] and ends with nums[right] having a neighbor $-\infty$. Therefore, a local maximum must exist in [mid+1, right]. We reduce the search space to this range.
   • If nums[mid] > nums[mid+1], the slope is falling at mid. The subarray nums[left...mid] ends with nums[mid] > nums[mid+1] and starts with nums[left] having a neighbor $-\infty$. A local maximum must exist in [left, mid]. We reduce the search space to this range.
3. Termination: The search space size decreases strictly in each step. When left == right, the search space is size 1. Due to the invariant, this single element must be a peak.

Pattern Reuse Notes

The Binary Search pattern, specifically analyzing local properties to discard halves of the array, is applicable to several other popular interview questions:

• LeetCode 33: Search in Rotated Sorted Array - Uses a similar check to determine which half of the array is sorted to decide where to search.
• LeetCode 81: Search in Rotated Sorted Array II - Handles duplicates while applying the same logic as Problem 33.
• LeetCode 153: Find Minimum in Rotated Sorted Array - Identical subpattern; compares mid against right to find the inflection point (minimum) where the rotation occurred.
• LeetCode 162: Find Peak Element - The problem discussed here, using local slope gradients.

Reference Implementation

C++ Solution for LeetCode 162

1class Solution {
2public:
3    int findPeakElement(vector<int>& nums) {
4        int left = 0;
5        int right = nums.size() - 1;
6
7        // Maintain the invariant that a peak element lies within [left, right]
8        while (left < right) {
9            int mid = left + (right - left) / 2;
10
11            // Compare mid with its right neighbor
12            if (nums[mid] < nums[mid + 1]) {
13                // We are on an upward slope. The peak must be to the right.
14                // mid cannot be the peak, so we exclude it.
15                left = mid + 1;
16            } else {
17                // We are on a downward slope (or mid is the peak).
18                // The peak is either at mid or to the left.
19                right = mid;
20            }
21        }
22
23        // When left == right, we have found the peak position
24        return left;
25    }
26};

Java Solution for LeetCode 162

1class Solution {
2    public int findPeakElement(int[] nums) {
3        int left = 0;
4        int right = nums.length - 1;
5
6        // Binary search loop
7        while (left < right) {
8            // Calculate mid to avoid potential overflow
9            int mid = left + (right - left) / 2;
10
11            // Check if we are in an ascending sequence
12            if (nums[mid] < nums[mid + 1]) {
13                // Peak is in the right half, exclude mid
14                left = mid + 1;
15            } else {
16                // Peak is in the left half or is mid
17                right = mid;
18            }
19        }
20
21        // left and right converge to the peak index
22        return left;
23    }
24}

Python Solution for LeetCode 162

1class Solution:
2    def findPeakElement(self, nums: List[int]) -> int:
3        left, right = 0, len(nums) - 1
4        
5        while left < right:
6            mid = left + (right - left) // 2
7            
8            # Compare mid with its right neighbor
9            if nums[mid] < nums[mid + 1]:
10                # Ascending slope: peak is to the right
11                left = mid + 1
12            else:
13                # Descending slope: peak is to the left or at mid
14                right = mid
15                
16        # When the loop ends, left == right, pointing to the peak
17        return left