Find the Peaks - Video Solutions

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.