Problem

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 ofpeaks 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.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5
6

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 <= 100
  • 1 <= mountain[i] <= 100

Solution

Method 1 – Simple Linear Scan

Intuition

A peak is an element that is strictly greater than its neighbors. Since the first and last elements cannot be peaks, we only need to check elements from index 1 to n-2.

Approach

  1. Iterate through the array from index 1 to n-2.
  2. For each index i, check if mountain[i] > mountain[i-1] and mountain[i] > mountain[i+1].
  3. If so, add i to the answer list.
  4. Return the list of peak indices.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    vector<int> findPeaks(vector<int>& mountain) {
        vector<int> ans;
        int n = mountain.size();
        for (int i = 1; i + 1 < n; ++i) {
            if (mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1])
                ans.push_back(i);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func findPeaks(mountain []int) []int {
    n := len(mountain)
    ans := []int{}
    for i := 1; i+1 < n; i++ {
        if mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1] {
            ans = append(ans, i)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public List<Integer> findPeaks(int[] mountain) {
        List<Integer> ans = new ArrayList<>();
        int n = mountain.length;
        for (int i = 1; i + 1 < n; ++i) {
            if (mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1])
                ans.add(i);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun findPeaks(mountain: IntArray): List<Int> {
        val ans = mutableListOf<Int>()
        for (i in 1 until mountain.size - 1) {
            if (mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1])
                ans.add(i)
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def findPeaks(self, mountain: list[int]) -> list[int]:
        n = len(mountain)
        ans = []
        for i in range(1, n-1):
            if mountain[i] > mountain[i-1] and mountain[i] > mountain[i+1]:
                ans.append(i)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn find_peaks(mountain: Vec<i32>) -> Vec<i32> {
        let n = mountain.len();
        let mut ans = vec![];
        for i in 1..n-1 {
            if mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1] {
                ans.push(i as i32);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    findPeaks(mountain: number[]): number[] {
        const n = mountain.length;
        const ans: number[] = [];
        for (let i = 1; i + 1 < n; ++i) {
            if (mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1])
                ans.push(i);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each element is checked once.
  • 🧺 Space complexity: O(1) — Output list aside, no extra space is used.