2951. Find the Peaks
Problem Description
In this problem, we are given a 0-indexed integer array named mountain
. Our goal is to identify all the elements in the array that qualify as "peaks". A peak in the mountain
array is an element that is strictly greater than its immediate neighbors to the left and right. We are tasked with returning an array containing the indices of all such peaks. It's important to note that according to the problem rules, the first element (at index 0) and the last element (at the end of the array) cannot be considered as peaks regardless of their value compared to adjacent elements.
Intuition
The intuition behind the solution strategy for this problem involves iterating through the array and examining elements that have neighboring elements on both sides ā this means starting our assessment from the second element (index 1) and concluding it with the second-to-last element (as the first and last elements cannot be peaks). For each element at index i
, where 1 <= i < len(mountain) - 1
, we check the following condition: is the current element greater than the element on its left (mountain[i - 1]
) and greater than the element on its right (mountain[i + 1]
)? If both these conditions are met, then the element at index i
is considered a peak, and we add its index i
to our list of peaks. This process is repeated for all eligible elements in the array. After we've checked all elements, we return the list of indices that correspond to the peaks we've found.
This direct traversal approach is straightforward and intuitive because it's based on the definition of a peak: an element that is larger than its immediate neighbors. By closely adhering to this definition and iterating through the array while applying this check, we can compile a list of all indices that are peaks.
Solution Approach
The solution for finding all peaks in the mountain
array is implemented through a simple for-loop that iterates over the indices of the array from index 1
to len(mountain) - 2
, inclusively. The reasoning behind starting the loop at index 1
and ending at len(mountain) - 2
is that the first and last elements cannot be peaks by definition, so they are automatically excluded from consideration.
Now, let's discuss the data structures and patterns used in the implementation:
-
Data Structures: The primary data structure used here is the array (or
List
in Python), both for the input (mountain
) and output (to store the indices of the peaks). Arrays are ideal for this solution because they allow us to access elements by their index efficiently, which is essential for comparing an element with its neighbors. -
Algorithm/Pattern: The core pattern here is a simple linear scan of the array, which is a basic algorithmic strategy. At each index
i
being considered by the loop, we apply the definition of a "peak":- To determine if the element at the current index
i
is a peak, we perform two comparisons:- Check if the element is greater than the element at index
i - 1
(to the left), denoted asmountain[i] > mountain[i - 1]
. - Check if the element is also greater than the element at index
i + 1
(to the right), denoted asmountain[i] > mountain[i + 1]
.
- Check if the element is greater than the element at index
- To determine if the element at the current index
If both conditions are true, we conclude that we have found a peak, and the index i
of this peak is added to the output list.
-
Implementation: Below is the implementation based on the description provided in the Reference Solution Approach:
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] ]
This Python implementation makes use of list comprehension, which is a concise way to create lists based on existing lists. It is used here to generate the list of peak indices in a single line of code.
The efficiency of this approach comes from the fact that every element is checked only once, and there are no nested loops, which means that the runtime complexity is linear O(n), where n
is the number of elements in the mountain
array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example mountain
array to illustrate the solution approach:
Suppose our initial mountain
array is [2, 3, 5, 4, 1, 3, 2, 4]
.
Now, following our solution approach, we will look for peaks, which are elements higher than their immediate neighbors:
- Start at index 1 with the value
3
and compare it to its neighbors. Its left neighbor is2
and right neighbor is5
. Since3
is not greater than5
, it is not a peak. - Move to index 2 with the value
5
. The left neighbor is3
and the right neighbor is4
.5
is greater than both3
and4
, so index2
is a peak. - Next, at index 3 with the value
4
, we compare it to its neighbors5
(left) and1
(right). As4
is not greater than5
, it is therefore not a peak. - Proceed to index 4, the value
1
is not a peak since its left neighbor4
is greater. - At index 5 with the value
3
, we compare it to the neighbors1
(left) and2
(right).3
is greater than both1
and2
, making index5
a peak. - Then, at index 6 with the value
2
, it has neighbors3
(left) and4
(right). Since2
is less than3
, it's not a peak. - Lastly, we do not consider index 7 as it's the end of the array and by rule can't be a peak.
The output based on our solution approach should, therefore, be a list of indices that are peaks, in this case, [2, 5]
.
In this example, we demonstrated the linear scan approach mentioned in the solution strategy. We iterated over the array elements (skipping the first and last ones), compared each element to its neighbors, and found the peaks by checking if they are greater than both the element immediately to their left and right. The simplicity of this algorithm allows it to run with O(n) complexity where n is the length of the mountain
array, because each element is checked only once.
Solution Implementation
1# Define the Solution class
2class Solution:
3 def find_peaks(self, mountain: List[int]) -> List[int]:
4 # This method finds and returns the indices of all peak elements in the given mountain list.
5 # A peak element is one that is strictly greater than its neighbors.
6
7 # Initialize a list to store the indices of the peak elements
8 peaks_indices = []
9
10 # Iterate through the mountain list, starting from the second element and ending at the second to last
11 for i in range(1, len(mountain) - 1):
12 # Check if the current element is a peak, i.e., it is greater than its left and right neighbors
13 if mountain[i - 1] < mountain[i] > mountain[i + 1]:
14 # If it's a peak, append the index to the peaks_indices list
15 peaks_indices.append(i)
16
17 # Return the list of peak indices
18 return peaks_indices
19
20# Note: Before using the code, make sure to import the `List` type from the `typing` module like this:
21# from typing import List
22
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5
6 /**
7 * Finds and returns a list of indices representing peak elements in a given array.
8 * A peak element is an element which is greater than its neighbors.
9 *
10 * @param mountain An array representing the heights of the mountain at each point.
11 * @return A list of integers representing the indices of the peak elements.
12 */
13 public List<Integer> findPeaks(int[] mountain) {
14 // The list to store indices of peak elements.
15 List<Integer> peaks = new ArrayList<>();
16
17 // Iterate over the array elements, starting from the second element and
18 // ending at the second last element, to avoid out-of-bounds situations.
19 for (int i = 1; i < mountain.length - 1; ++i) {
20 // Compare the current element with its neighbors to check if it's a peak.
21 if (mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1]) {
22 // If it's a peak, add its index to the list.
23 peaks.add(i);
24 }
25 }
26
27 // Return the list of peak indices.
28 return peaks;
29 }
30}
31
1#include <vector>
2
3class Solution {
4public:
5 // Function to find all the peak elements of a given vector 'mountain'
6 // and return their indices.
7 std::vector<int> findPeaks(std::vector<int>& mountain) {
8 std::vector<int> peaks; // Vector to store the indices of the peaks
9
10 // Iterate through the elements of the array, starting from the second element
11 // and ending at the second to last element.
12 for (int i = 1; i < mountain.size() - 1; ++i) {
13 // Check if the current element is larger than the one before it
14 // and the one after it, which makes it a peak.
15 if (mountain[i - 1] < mountain[i] && mountain[i + 1] < mountain[i]) {
16 peaks.push_back(i); // If it is a peak, add its index to the 'peaks' vector
17 }
18 }
19
20 return peaks; // Return the vector with the indices of all peaks
21 }
22};
23
1/**
2 * Identifies the peak elements in a mountain array.
3 * A peak element is defined as an element that is greater than its neighbors.
4 * @param {number[]} mountain - The array representing the mountain with heights as elements.
5 * @returns {number[]} Indices of all peak elements in the mountain array.
6 */
7function findPeaks(mountain: number[]): number[] {
8 // Initialize an array to store the indices of peak elements.
9 const peaks: number[] = [];
10
11 // Iterate through the array starting from the second element and ending at the second to last element.
12 for (let i = 1; i < mountain.length - 1; ++i) {
13 // Check if the current element is greater than its immediate neighbors.
14 if (mountain[i - 1] < mountain[i] && mountain[i + 1] < mountain[i]) {
15 // If the current element is a peak, add its index to the peaks array.
16 peaks.push(i);
17 }
18 }
19
20 // Return the array of peak elements' indices.
21 return peaks;
22}
23
Time and Space Complexity
The given code snippet is designed to find the peaks in a list of integers representing elevations in a mountain sequence. A peak is defined as an element that is greater than its immediate neighbors.
Time Complexity
The function findPeaks
iterates over the input mountain
list exactly once, starting from index 1 and ending at len(mountain) - 1
. For each element, it performs a constant time comparison with its neighbors. This results in a linear time complexity relative to the size of the input list. Therefore, the time complexity of the function is O(n)
, where n
is the length of the mountain
list.
Space Complexity
The space complexity of the function consists of two parts: additional data structures used within the function and the output list. Since no additional data structures are used other than the output list, and ignoring the output list's space, the space complexity is O(1)
. This implies that the function consumes a constant amount of space, irrespective of the size of the input list.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!