Difficulty: Easy | Acceptance: 75.20% | Paid: No Topics: Array, Enumeration
You are given a 0-indexed array mountain. Your task is to find all the peaks in the array.
Return an array that consists of indices of peaks in increasing order.
An index i is a peak if:
0 < i < mountain.length - 1 mountain[i - 1] < mountain[i] mountain[i] > mountain[i + 1]
- Examples
- Constraints
- Linear Scan
- Functional Approach
Examples
Example 1:
Input: mountain = [2,4,4]
Output: []
Explanation: mountain[0] and mountain[1] are both not peaks because they are not strictly greater than their neighbors. mountain[2] is also not a peak because it is not strictly greater than mountain[1].
Example 2:
Input: mountain = [1,4,3,8,5]
Output: [1,3]
Explanation: mountain[1] is a peak because 4 is strictly greater than 1 and 3. mountain[3] is a peak because 8 is strictly greater than 3 and 5.
Constraints
3 <= mountain.length <= 100
1 <= mountain[i] <= 100
Linear Scan
Intuition We iterate through the array once, checking every element (except the first and last) to see if it satisfies the peak condition.
Steps
- Initialize an empty list to store peak indices.
- Iterate from index 1 to the second-to-last index (length - 2).
- For each index, check if the current element is strictly greater than both its left and right neighbors.
- If the condition is met, add the index to the result list.
- Return the result list.
python
class Solution:
def findPeaks(self, mountain: list[int]) -> list[int]:
peaks = []
n = len(mountain)
for i in range(1, n - 1):
if mountain[i - 1] < mountain[i] and mountain[i] > mountain[i + 1]:
peaks.append(i)
return peaks
Complexity
- Time: O(n)
- Space: O(1) (excluding the output list)
- Notes: This is the most efficient approach as we must inspect every element to determine if it is a peak.
Functional Approach
Intuition Utilize built-in functional programming constructs like filter, map, or comprehensions to declaratively select indices that meet the peak criteria.
Steps
- Generate a sequence of valid indices (from 1 to n-2).
- Filter this sequence based on the condition that the element at that index is greater than its neighbors.
- Collect the filtered indices into a list.
python
class Solution:
def findPeaks(self, mountain: list[int]) -> list[int]:
return [i for i in range(1, len(mountain) - 1) if mountain[i - 1] < mountain[i] > mountain[i + 1]]
Complexity
- Time: O(n)
- Space: O(1) (excluding the output list)
- Notes: While syntactically different, the underlying complexity remains linear. This approach often improves readability for those familiar with functional paradigms.