# Find the Peaks
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-peaks)
Canonical: https://scaleengineer.com/dsa/problems/find-the-peaks
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
---
## 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 _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 <= 100`
* `1 <= mountain[i] <= 100`

# Approaches
## Single Pass Iteration
The problem requires us to find all 'peaks' in an array, where a peak is an element strictly greater than its immediate neighbors. The problem statement also specifies that the first and last elements of the array cannot be peaks. This simplifies the problem by removing the need to handle boundary conditions for neighbors.

The most direct and efficient solution is to perform a single pass through the array. We can iterate from the second element to the second-to-last element and, for each element, check if it satisfies the peak condition.
**Time:** O(N), where N is the length of the `mountain` array. This is because we iterate through the array once from the second element to the second-to-last element. · **Space:** O(K), where K is the number of peaks. In the worst-case scenario (e.g., `[5, 1, 5, 1, ...]`), the number of peaks can be up to `(N-1)/2`, making the space complexity O(N) in the worst case. If the space for the output is not counted, the space complexity is O(1).
**Pros:** It is the most time-efficient solution, as it requires visiting each element only once.; The space complexity is optimal, as it only requires extra space for the output list.; The logic is simple, straightforward, and easy to implement.
**Cons:** For this particular problem, the straightforward approach is also the most optimal, so there are no significant disadvantages.
### Explanation
This approach involves a linear scan of the array to identify all elements that meet the definition of a peak.

We can set up a loop that runs from index `1` to `length - 2` of the input array `mountain`. This range covers all elements that have both a left and a right neighbor, which is a prerequisite for being a peak as defined.

Inside the loop, for each element `mountain[i]`, we perform a simple comparison: `mountain[i] > mountain[i-1]` and `mountain[i] > mountain[i+1]`. If this condition evaluates to true, we have found a peak, and we add its index `i` to a result list.

After checking all the elements in the specified range, the list of collected indices is returned.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    /**
     * Finds all the peaks in a mountain array.
     * A peak is an element that is strictly greater than its neighbors.
     * The first and last elements are not considered peaks.
     *
     * @param mountain The input array of integers.
     * @return A list of indices of the peaks.
     */
    public List<Integer> findPeaks(int[] mountain) {
        List<Integer> peaks = new ArrayList<>();
        // We only need to check elements from index 1 to mountain.length - 2
        // because the first and last elements cannot be peaks.
        for (int i = 1; i < mountain.length - 1; i++) {
            // Check if the current element is strictly greater than its left and right neighbors.
            if (mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1]) {
                peaks.add(i);
            }
        }
        return peaks;
    }
}
```
### Algorithm
1. Initialize an empty list, `peakIndices`, to store the indices of the peaks found.
2. Iterate through the `mountain` array using an index `i`, starting from `1` and ending at `mountain.length - 2`. The first and last elements are skipped as they cannot be peaks.
3. In each iteration, check if the element `mountain[i]` is strictly greater than its left neighbor `mountain[i-1]` and its right neighbor `mountain[i+1]`.
4. If the condition `mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1]` is met, it signifies a peak. Add the index `i` to the `peakIndices` list.
5. After the loop has processed all potential peak elements, return the `peakIndices` list.

# Solutions
### Java

```java
class Solution { public List < Integer > findPeaks ( int [] mountain ) { List < Integer > ans = new ArrayList <>(); for ( int i = 1 ; i < mountain . length - 1 ; ++ i ) { if ( mountain [ i - 1 ] < mountain [ i ] && mountain [ i + 1 ] < mountain [ i ]) { ans . add ( i ); } } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  vector<int> findPeaks(vector<int> &mountain) {
    vector<int> ans;
    for (int i = 1; i < mountain.size() - 1; ++i) {
      if (mountain[i - 1] < mountain[i] && mountain[i + 1] < mountain[i]) {
        ans.push_back(i);
      }
    }
    return ans;
  }
};

```

### Python

```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]]

```