Find the Peaks - Solution & Explanation
Problem Statement
You are given a 0-indexed array mountain. Your task is to find all the peaks in the mountain array.
Return an array that consists of indices of peaks in the given array in any order.
Notes:
- A peak is defined as an element that is strictly greater than its neighboring elements.
- The first and last elements of the array are not a peak.
Example 1:
Input: mountain = [2,4,4] Output: [] Explanation: mountain[0] and mountain[2] can not be a peak because they are first and last elements of the array. mountain[1] also can not be a peak because it is not strictly greater than mountain[2]. So the answer is [].
Example 2:
Input: mountain = [1,4,3,8,5] Output: [1,3] Explanation: mountain[0] and mountain[4] can not be a peak because they are first and last elements of the array. mountain[2] also can not be a peak because it is not strictly greater than mountain[3] and mountain[1]. But mountain [1] and mountain[3] are strictly greater than their neighboring elements. So the answer is [1,3].
Constraints:
3 <= mountain.length <= 1001 <= mountain[i] <= 100
Approach Overview
Problem Overview: You are given an integer array mountain. A peak is an index i such that mountain[i] is strictly greater than both neighbors: mountain[i-1] and mountain[i+1]. The first and last elements cannot be peaks because they do not have two neighbors. Your task is to return all indices that satisfy this condition.
Approach 1: Brute Force Neighbor Check (O(n) time, O(1) extra space)
The straightforward approach is to iterate through the array and check each valid index against its immediate neighbors. Start from index 1 and stop at n-2. For every index i, compare mountain[i] with mountain[i-1] and mountain[i+1]. If the current value is strictly greater than both, record i in the result list.
This method directly follows the problem definition. It performs two comparisons per index and uses only a result container to store peak indices. Since each element is checked once, the time complexity is O(n) and the auxiliary space (excluding output) is O(1). This approach is simple and reliable for small and large inputs alike.
Approach 2: Optimized Single Pass Enumeration (O(n) time, O(1) extra space)
The optimized version treats the problem as a single-pass scan over the array using array traversal and enumeration. Instead of thinking of it as a repeated "check," you maintain a forward iteration and evaluate the peak condition inline during traversal.
Initialize an empty list for the results and loop from i = 1 to n - 2. For each position, perform two comparisons: check whether the current value is greater than the previous element and the next element. When both conditions hold, append the index to the result. The algorithm performs exactly one pass and does not require additional data structures.
The complexity remains O(n) time and O(1) extra space because each element is visited once and only constant additional memory is used. The difference from the brute-force mindset is conceptual clarity: this approach frames the problem as a clean linear scan with constant checks, which is how most interview solutions are written.
Recommended for interviews: The single-pass enumeration approach is what interviewers expect. It demonstrates that you can translate the definition of a peak directly into a linear scan using simple comparisons. Mentioning the brute-force reasoning first shows you understand the problem constraints, but implementing the O(n) single-pass solution highlights strong fundamentals with arrays and efficient iteration patterns.
Approach 1: Brute Force Approach
This approach involves iterating through the given array and checking each element to find the peaks. A peak is defined as an element that is strictly greater than its neighboring elements. Specifically, an element at index i is a peak if mountain[i] > mountain[i-1] and mountain[i] > mountain[i+1]. We must ensure that we do not check the first or last elements, as they cannot be peaks. The time complexity of this approach is O(n), where n is the number of elements in the mountain array, because we make one pass through the array. The space complexity is O(1), as we use a constant amount of extra memory.
The solution involves iterating through each element from the second to the second last element of the array. We check if the current element is strictly greater than its neighboring elements. If it is, we store the index in a dynamically allocated array and increase the return size. Finally, we return this array of indices.
Complexity
Time Complexity: O(n)
Space Complexity: O(n) for the dynamic array to store the peaks.
Approach 2: Optimized Single Pass Approach
This approach aims to optimize by reducing redundant checks and utilizing a single iteration efficiently. Given the constraints, the optimized solution also iterates through the array but takes extra care to minimize checks by assuming certain boundaries have already been met. The time complexity is similar to the brute force approach at O(n), but we attempt to improve constant factors. The space complexity remains O(1) for constant auxiliary space, but realistic implementations use O(n) for output storage.
This single-pass, optimized solution follows a similar logic to the brute force method but with minor optimizations that reduce overhead from conditional checks without altering the O(n) complexity and assuming redundancy might help in micro-optimizations in alternative settings. The approach scans and efficiently stores indices of peaks using minimal logic checks.
Complexity
Time Complexity: O(n)
Space Complexity: O(n) for the storage of results.
Approach 3: Direct Traversal
We directly traverse the index i \in [1, n-2]. For each index i, if mountain[i-1] < mountain[i] and mountain[i + 1] < mountain[i], then mountain[i] is a peak, and we add index i to the answer array.
After the traversal ends, we return the answer array.
The time complexity is O(n), where n is the length of the array. Ignoring the space consumption of the answer array, the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n) |
| Optimized Single Pass Approach | Time Complexity: O(n) |
| Direct Traversal | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Neighbor Check | O(n) | O(1) | When implementing the definition directly or explaining the problem step-by-step in interviews. |
| Optimized Single Pass Enumeration | O(n) | O(1) | Preferred production and interview solution. Clean linear scan with minimal comparisons. |
Video Solution
Solving Leetcode 2951 in Swift – Find the Peaks • BABE ENGINEER • 1,293 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Peaks easy or hard?
Find the Peaks Python/Java solution
How to solve Find the Peaks in O(n)?
What is the best approach for Find the Peaks?
Is Find the Peaks asked at Google/Amazon/Meta?
What data structure is used in Find the Peaks?
What is the time complexity of Find the Peaks?
Ready to solve this problem?
Practice Find the Peaks with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor