Problem Description

You are given a 0-indexed array called mountain. Your task is to find all the peaks in this array.

A peak is defined as an element that is strictly greater than both of its neighboring elements. In other words, for an element at index i to be a peak, it must satisfy: mountain[i-1] < mountain[i] and mountain[i] > mountain[i+1].

Important constraints:

• The first element (index 0) and the last element (index n-1) of the array cannot be peaks since they don't have two neighbors
• You need to return an array containing the indices of all peaks found
• The indices can be returned in any order

For example, if mountain = [1, 3, 2, 4, 1], then:

• Index 1 (value 3) is a peak because 1 < 3 > 2
• Index 3 (value 4) is a peak because 2 < 4 > 1
• So the answer would be [1, 3]

The solution uses a straightforward approach: iterate through all valid indices from 1 to len(mountain) - 2, and for each index i, check if mountain[i] is greater than both mountain[i-1] and mountain[i+1]. If this condition is met, add index i to the result list.

Intuition

The problem asks us to find elements that are "higher" than both their neighbors - like mountain peaks in a landscape. Since we need to compare each element with both its left and right neighbors, we immediately know that the first and last elements can't be peaks (they only have one neighbor each).

The natural approach is to check every possible position that could be a peak. We can't check index 0 or index n-1, so we only need to examine indices from 1 to n-2.

For each position i in this range, we simply need to verify if it forms a peak by checking:

• Is mountain[i] greater than mountain[i-1]? (higher than left neighbor)
• Is mountain[i] greater than mountain[i+1]? (higher than right neighbor)

If both conditions are true, we've found a peak at index i.

This direct checking approach works because:

1. Each peak is independent - finding one peak doesn't affect whether another position is a peak
2. We only need local information (the element and its two neighbors) to determine if a position is a peak
3. There's no need for any preprocessing or complex logic - just a simple comparison at each valid position

The elegance of this solution comes from recognizing that we can express both conditions in a single chained comparison: mountain[i-1] < mountain[i] > mountain[i+1], which reads naturally as "the middle element is greater than both sides."

Solution Approach

The implementation follows a direct traversal approach to identify all peaks in the mountain array.

Algorithm Steps:

1. Define the search range: Since peaks cannot be at the first or last positions, we iterate through indices from 1 to len(mountain) - 2.

2. Check peak condition: For each index i in this range, we verify if the element at position i satisfies the peak condition:

   • mountain[i-1] < mountain[i] (greater than left neighbor)
   • mountain[i] > mountain[i+1] (greater than right neighbor)

3. Collect results: If both conditions are met, we add the index i to our result list.

Implementation Details:

The solution uses a list comprehension for concise implementation:

return [
    i
    for i in range(1, len(mountain) - 1)
    if mountain[i - 1] < mountain[i] > mountain[i + 1]
]

Breaking down the components:

• range(1, len(mountain) - 1): Generates indices from 1 to n-2, where n is the array length
• mountain[i - 1] < mountain[i] > mountain[i + 1]: Python's chained comparison elegantly checks both conditions simultaneously
• The list comprehension automatically collects all indices where the condition is true

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the mountain array, as we visit each internal element exactly once
• Space Complexity: O(1) extra space (not counting the output array), as we only use a constant amount of additional variables

The beauty of this approach lies in its simplicity - no need for auxiliary data structures or complex logic, just a straightforward scan through the array with local comparisons.

Example Walkthrough

Let's walk through the solution with the array mountain = [2, 1, 3, 5, 4, 6, 2].

Step 1: Identify the valid range

• Array length: 7
• Valid indices to check: 1 through 5 (since indices 0 and 6 cannot be peaks)

Step 2: Check each position

• Index 1 (value = 1):

  • Left neighbor: mountain[0] = 2
  • Current: mountain[1] = 1
  • Right neighbor: mountain[2] = 3
  • Check: Is 2 < 1 > 3? → No (1 is not greater than 2)
  • Not a peak ✗

• Index 2 (value = 3):

  • Left neighbor: mountain[1] = 1
  • Current: mountain[2] = 3
  • Right neighbor: mountain[3] = 5
  • Check: Is 1 < 3 > 5? → No (3 is not greater than 5)
  • Not a peak ✗

• Index 3 (value = 5):

  • Left neighbor: mountain[2] = 3
  • Current: mountain[3] = 5
  • Right neighbor: mountain[4] = 4
  • Check: Is 3 < 5 > 4? → Yes (5 > 3 and 5 > 4)
  • Peak found! ✓

• Index 4 (value = 4):

  • Left neighbor: mountain[3] = 5
  • Current: mountain[4] = 4
  • Right neighbor: mountain[5] = 6
  • Check: Is 5 < 4 > 6? → No (4 is not greater than 5)
  • Not a peak ✗

• Index 5 (value = 6):

  • Left neighbor: mountain[4] = 4
  • Current: mountain[5] = 6
  • Right neighbor: mountain[6] = 2
  • Check: Is 4 < 6 > 2? → Yes (6 > 4 and 6 > 2)
  • Peak found! ✓

Step 3: Collect results The peaks are found at indices 3 and 5.

Final Answer: [3, 5]

The algorithm efficiently scans through each valid position once, checking only the immediate neighbors to determine if each element forms a peak in the mountain array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array mountain. The algorithm iterates through the array once from index 1 to n-2, checking each element against its neighbors. Each comparison operation takes constant time O(1), resulting in a total time complexity of O(n).

Space Complexity: O(1) if we exclude the space used for the output list. The algorithm uses a list comprehension that only requires a constant amount of extra space for the loop variable i and temporary comparisons. The space consumed by the returned list containing the peak indices is not counted as part of the auxiliary space complexity, as it's considered part of the output.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Boundary Handling

One of the most frequent mistakes is attempting to check peaks at the array boundaries or incorrectly setting the iteration range.

Incorrect Implementation:

# Wrong: Includes first and last elements
for i in range(len(mountain)):
    if mountain[i-1] < mountain[i] > mountain[i+1]:  # IndexError!
        peaks.append(i)

Why it fails: When i = 0, accessing mountain[i-1] results in mountain[-1] (last element), and when i = len(mountain)-1, accessing mountain[i+1] causes an IndexError.

Correct Solution:

# Start from index 1 and stop before the last index
for i in range(1, len(mountain) - 1):
    if mountain[i-1] < mountain[i] > mountain[i+1]:
        peaks.append(i)

2. Using Non-Strict Comparisons

Another common error is using <= or >= instead of strict inequalities.

Incorrect Implementation:

# Wrong: Uses non-strict comparison
if mountain[i-1] <= mountain[i] >= mountain[i+1]:
    peaks.append(i)

Why it fails: This would incorrectly identify plateaus (consecutive equal elements) as peaks. For example, in [1, 2, 2, 1], index 1 would be incorrectly marked as a peak.

Correct Solution:

# Use strict inequalities
if mountain[i-1] < mountain[i] > mountain[i+1]:
    peaks.append(i)

3. Handling Edge Cases Incorrectly

Failing to consider arrays with insufficient length.

Problematic Assumption:

def findPeaks(self, mountain: List[int]) -> List[int]:
    peaks = []
    # Assumes array has at least 3 elements
    for i in range(1, len(mountain) - 1):
        if mountain[i-1] < mountain[i] > mountain[i+1]:
            peaks.append(i)
    return peaks

Why it could be better: While the range handles empty iterations gracefully when len(mountain) < 3, explicitly handling this case improves code clarity.

More Robust Solution:

def findPeaks(self, mountain: List[int]) -> List[int]:
    # Early return for arrays too small to have peaks
    if len(mountain) < 3:
        return []
  
    peaks = []
    for i in range(1, len(mountain) - 1):
        if mountain[i-1] < mountain[i] > mountain[i+1]:
            peaks.append(i)
    return peaks

4. Returning Values Instead of Indices

A conceptual mistake where the peak values are returned instead of their indices.

Incorrect Implementation:

# Wrong: Returns values, not indices
if mountain[i-1] < mountain[i] > mountain[i+1]:
    peaks.append(mountain[i])  # Should be i, not mountain[i]

Correct Solution:

# Return the index, not the value
if mountain[i-1] < mountain[i] > mountain[i+1]:
    peaks.append(i)