Problem Description
You are given a 0-indexed array mountain. Your task is to find all the peaks in the mountain array. 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 considered peaks. Return an array containing the indices of all peaks in any order.
Key Insights
- The first and last elements are excluded from being peaks.
- A peak must be strictly greater than both its left and right neighbors.
- Iterate through the array once, starting from the second element and ending the iteration at the second-last element.
- The problem can be efficiently solved in O(n) time, with O(p) space for collecting the peak indices, where p is the number of peaks.
Space and Time Complexity
Time Complexity: O(n), where n is the number of elements in the mountain array. Space Complexity: O(p), where p is the number of peaks stored in the result (worst-case O(n) if all non-boundary elements are peaks).
Solution
The solution involves iterating through the array starting from index 1 and ending at index n-2. For each element, we check if it is strictly greater than its immediate neighbors (elements at i-1 and i+1). If it is, we add its index to our result list. This process ensures we correctly capture all peak indices in a single pass, resulting in efficient linear time complexity and minimal space usage beyond the output array.