Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Find Peak Element

MEDIUMProblemSolveExternal Links

Description

A peak element in an array is an element that is strictly greater than both of its neighbors.

Given a 0-indexed integer array nums, find any peak element and return its index. If the array contains multiple peaks, you may return the index of any one of them.

The elements just outside the array boundaries are treated as negative infinity. Formally, nums[-1] = -∞ and nums[n] = -∞. This means the first element only needs to be greater than the second element to qualify as a peak, and the last element only needs to be greater than the second-to-last element.

It is guaranteed that no two adjacent elements are equal, which ensures that at least one peak always exists.

You must write an algorithm that runs in O(log n) time.

Examples

Example 1

Input: nums = [1, 2, 3, 1]

Output: 2

Explanation: nums[2] = 3 is a peak element because 3 > 2 (left neighbor) and 3 > 1 (right neighbor). Index 2 is the only peak in this array.

Example 2

Input: nums = [1, 2, 1, 3, 5, 6, 4]

Output: 5

Explanation: nums[5] = 6 is a peak element because 6 > 5 (left neighbor) and 6 > 4 (right neighbor). Returning index 1 would also be accepted, since nums[1] = 2 is also a peak (2 > 1 on both sides).

Example 3

Input: nums = [5, 4, 3, 2, 1]

Output: 0

Explanation: nums[0] = 5 is a peak because its left neighbor is considered -∞ (outside the array) and 5 > 4 (right neighbor). In a strictly decreasing array, the first element is always a peak.

Constraints

  • 1 ≤ nums.length ≤ 1000
  • -2^31 ≤ nums[i] ≤ 2^31 - 1
  • nums[i] ≠ nums[i + 1] for all valid i

Editorial

Brute Force

Intuition

The simplest way to find a peak is to walk through the array from left to right and check each element against its neighbors. Since the boundaries are treated as negative infinity, the array effectively "starts from -∞ and must return to -∞." This means if the array ever goes up and then comes down, the turning point is a peak.

A helpful observation simplifies the check: because nums[-1] = -∞, the array begins by rising (conceptually). We just need to find the first place where the array stops rising — that is, the first index i where nums[i] > nums[i + 1]. At that point, nums[i] must be a peak:

  • It is greater than its right neighbor (we just checked that).
  • It is greater than its left neighbor (because we never returned earlier, meaning every previous element was less than its right neighbor, so the sequence was still climbing up to index i).

If we reach the last element without finding such a drop, then the entire array is strictly increasing, and the last element is the peak (since its right neighbor is -∞).

Step-by-Step Explanation

Let's trace through with nums = [1, 3, 5, 7, 8, 6, 4]:

Step 1: Start at index 0. Check: is nums[0] > nums[1]? Is 1 > 3? No. The sequence is still climbing. Move to the next index.

Step 2: Check index 1. Is nums[1] > nums[2]? Is 3 > 5? No. Still climbing.

Step 3: Check index 2. Is nums[2] > nums[3]? Is 5 > 7? No. Still climbing.

Step 4: Check index 3. Is nums[3] > nums[4]? Is 7 > 8? No. Still climbing.

Step 5: Check index 4. Is nums[4] > nums[5]? Is 8 > 6? YES! We found the first drop. The array was climbing from -∞ all the way to index 4, so nums[4] = 8 is greater than both its neighbors.

Step 6: Return index 4.

This example shows how the linear scan may need to check many pairs before finding the first drop. If the peak is near the end, we do nearly n comparisons.

Linear Scan — Finding the First Drop — Watch how we scan left to right through a mostly-increasing array, checking each adjacent pair. The first position where the value drops reveals a peak.

Now let's see the worst case — a strictly increasing array nums = [1, 2, 3, 4, 5]:

Step 1: Is nums[0]=1 > nums[1]=2? No.
Step 2: Is nums[1]=2 > nums[2]=3? No.
Step 3: Is nums[2]=3 > nums[3]=4? No.
Step 4: Is nums[3]=4 > nums[4]=5? No.
Step 5: We reached the end without finding a drop. The last element (index 4, value 5) must be the peak because its right neighbor is -∞.

This is the worst case: we checked every pair before concluding the last element is the peak.

Algorithm

  1. Iterate through the array from index 0 to n-2:
    • If nums[i] > nums[i + 1], return i (this is a peak)
  2. If no drop was found, return n-1 (the last element is the peak)

Code

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return n - 1;
    }
};
class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                return i
        return len(nums) - 1
class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return n - 1;
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case (a strictly increasing array), we compare every adjacent pair, visiting all n-1 pairs once. Each comparison is O(1), so the total time is O(n).

Space Complexity: O(1)

We only use a loop variable and no additional data structures. The space used does not grow with input size.

Why This Approach Is Not Efficient

The linear scan visits up to n-1 elements, which is O(n). The problem explicitly requires O(log n) time, so a linear approach does not meet the constraint.

The core inefficiency is that we inspect every element one by one without skipping any. We never use the information from one comparison to rule out a large portion of the array.

Key insight: when we compare nums[mid] with nums[mid + 1], the result tells us which half of the array must contain a peak. If nums[mid] < nums[mid + 1], the array is still climbing at mid, so a peak must exist somewhere to the right. Conversely, if nums[mid] > nums[mid + 1], the array is descending, so a peak must exist at mid or to the left. This is exactly the structure binary search exploits — each comparison eliminates half the search space, reducing time from O(n) to O(log n).

Optimal Approach - Binary Search

Intuition

At first glance, binary search seems impossible because the array is not sorted. However, we do not need sorted order — we only need a way to decide which half to search next.

Here is the key reasoning:

  1. The boundaries are -∞, so the array "starts from -∞" on the left and "ends at -∞" on the right.
  2. If at any position mid, we see that nums[mid] < nums[mid + 1], the array is going uphill at mid. Since the right boundary is -∞, the array must eventually come back down. The point where it transitions from climbing to falling is a peak — and that peak is somewhere in the right half.
  3. Conversely, if nums[mid] > nums[mid + 1], the array is going downhill at mid. By the same boundary argument applied to the left, a peak exists at mid or in the left half.

Think of it like hiking on a trail that starts from sea level and must return to sea level. If you are at a point where the trail is going uphill, you know there must be a summit ahead of you. If the trail is going downhill, the summit is behind you or right where you stand.

By always moving toward the "uphill" side, we are guaranteed to find a peak. Each step halves the search space, giving us O(log n) time.

Diagram showing how binary search narrows the search space to find a peak by always moving toward the uphill side
Diagram showing how binary search narrows the search space to find a peak by always moving toward the uphill side

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 1, 3, 5, 6, 4]:

Step 1: Initialize left = 0, right = 6.

Step 2: Compute mid = (0 + 6) / 2 = 3. Compare nums[3] = 3 with nums[4] = 5.

  • 3 < 5 → the array is climbing at mid. A peak must exist to the right.
  • Update: left = mid + 1 = 4.

Step 3: Compute mid = (4 + 6) / 2 = 5. Compare nums[5] = 6 with nums[6] = 4.

  • 6 > 4 → the array is falling at mid. A peak exists at mid or to the left.
  • Update: right = mid = 5.

Step 4: Compute mid = (4 + 5) / 2 = 4. Compare nums[4] = 5 with nums[5] = 6.

  • 5 < 6 → the array is still climbing. Move right.
  • Update: left = mid + 1 = 5.

Step 5: Now left = 5 and right = 5. The search space has collapsed to a single element. left == right, so we exit the loop.

Step 6: Return left = 5. Verify: nums[5] = 6, and 6 > 5 (left neighbor) and 6 > 4 (right neighbor). Confirmed peak!

Binary Search for Peak — Halving the Search Space — Watch how binary search eliminates half the array at each step by comparing the middle element with its right neighbor, always moving toward the uphill direction.

Algorithm

  1. Initialize left = 0 and right = n - 1
  2. While left < right:
    • Compute mid = (left + right) / 2
    • If nums[mid] > nums[mid + 1], the peak is at mid or to its left → set right = mid
    • Otherwise, the peak is to the right of mid → set left = mid + 1
  3. When left == right, the pointers have converged on a peak. Return left.

Code

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
};
class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                left = mid + 1
        
        return left
class Solution {
    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]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}

Complexity Analysis

Time Complexity: O(log n)

Each iteration of the while loop halves the search space. Starting with n elements, after one iteration we have n/2, then n/4, and so on. The loop runs at most log₂(n) times before left and right converge, giving O(log n) total time.

Space Complexity: O(1)

We only use three integer variables (left, right, mid) regardless of input size. No recursion or additional data structures are needed.