Find the Peaks

Easy

Asked by:

17 views

Topics:

Arrays

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The constraints mention the array length will be at least 3. Should I assume the input will always be valid, or should I handle cases like a `null` input or an array with fewer than three elements?
To clarify the 'strictly greater' condition, for an array with a plateau, such as `[1, 5, 5, 2]`, would either of the 5s be considered a peak, or do both fail the condition?
The examples use integers for the mountain heights. Can I assume the input array will always contain integers, or could there be other numeric types like floats to consider?
The problem notes that the first and last elements cannot be peaks. Does this imply that the search for peaks should be confined to the range of indices from 1 to length-2?
If no peaks are found, the first example shows the output should be an empty array. Is this the expected output for all scenarios where no peaks exist?

Brute Force Solution

Approach

To find all the peaks in a sequence of numbers, the simplest method is to check every number one by one. For each number, we just need to see if it's taller than its immediate neighbors on both sides.

Here's how the algorithm would work step-by-step:

Imagine the numbers are arranged in a single row, like a mountain range.
A peak must be taller than the point just before it and the point just after it, so the very first and very last points in the row can't be peaks.
Start with the second number in the row.
Look at its immediate neighbors: the one to its left and the one to its right.
If the current number is strictly greater than both of those neighbors, then it's a peak. Make a note of it.
Now, move to the next number in the row and repeat the same comparison with its neighbors.
Continue this process for every number in the row that has neighbors on both sides.
After checking all the possible candidates, the collection of numbers you've noted down is your final answer.

Code Implementation

def find_peaks(mountain):
    peak_indices = []

    # To be a peak, an element must have neighbors, so we skip the first and last elements.

    for current_index in range(1, len(mountain) - 1):

        # The core condition for an element to be a peak is being strictly larger than both its neighbors.

        if mountain[current_index] > mountain[current_index - 1] and mountain[current_index] > mountain[current_index + 1]:

            # If the current element satisfies the peak condition, we store its position.

            peak_indices.append(current_index)

    return peak_indices

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by a single pass through the input array of size n. To find the peaks, we iterate from the second element to the second-to-last, which means we visit approximately n elements. For each element considered, we perform a constant number of operations: two comparisons against its immediate neighbors. Because the work done for each element does not change with the size of the input, the total operations scale linearly with n, which simplifies to O(n).

Space Complexity

O(N) – The primary use of auxiliary space comes from the collection created to store the results, as described by 'Make a note of it'. Let N be the number of elements in the input sequence. In the worst-case scenario, such as an alternating high-low pattern, the number of peaks can be proportional to N. Therefore, the list holding the final answer can grow up to a size that is linearly dependent on the input size N.

Optimal Solution

Approach

The most efficient way to find the peaks is to perform a single, straightforward scan through the list of numbers. Since a peak is defined only by its immediate neighbors, we can check each number just once to see if it qualifies.

Here's how the algorithm would work step-by-step:

Imagine the numbers are a mountain range. A peak is a mountain that's taller than the ground on both its left and right side.
The very first and very last numbers in the list can't be peaks because they only have one neighbor to compare against, so we can ignore them.
Start by looking at the second number in the list.
Compare this number to the one immediately before it and the one immediately after it.
If the current number is greater than both of its neighbors, you have found a peak. Keep track of it.
Move to the next number in the list and repeat the same comparison with its neighbors.
Continue this process until you have checked every number that has two neighbors. The complete collection of peaks you've found is your answer.

Code Implementation

def find_peaks(mountain_heights):
    peak_indices = []

    # We only check interior numbers, as the first and last elements lack two neighbors.
    for current_index in range(1, len(mountain_heights) - 1):

        is_taller_than_left = mountain_heights[current_index] > mountain_heights[current_index - 1]
        is_taller_than_right = mountain_heights[current_index] > mountain_heights[current_index + 1]

        # A number is a peak if it is strictly greater than both of its immediate neighbors.
        if is_taller_than_left and is_taller_than_right:

            # If the conditions for a peak are met, we record its location (index).
            peak_indices.append(current_index)

    return peak_indices

Big(O) Analysis

Time Complexity

O(n) – Let n be the number of elements in the input list. The cost of the solution is driven by a single scan through the elements to check for peaks. We iterate from the second element to the second-to-last, visiting each of these n-2 elements exactly once. For each element, we perform a constant number of operations, specifically two comparisons against its immediate neighbors. Therefore, the total number of operations is directly proportional to n, which simplifies to a time complexity of O(n).

Space Complexity

O(N) – The auxiliary space is primarily determined by the collection used to store the results, as implied by the instruction to 'Keep track of' the found peaks. Let N be the number of elements in the input list. In the worst case, the number of peaks can be proportional to N, which means the list storing these peaks will also grow linearly with the input size. Aside from this output list, the algorithm only uses a few variables for the iteration, which consume a constant amount of space. Therefore, the space complexity is O(N) because the memory required for the results depends directly on the input size.

Edge Cases

Case	How to Handle
Input array has the minimum allowed length of 3	The solution correctly checks only the middle element at index 1 as a potential peak.
Input array has no peaks, such as a monotonically increasing or decreasing array	The loop will complete without finding any elements that satisfy the peak condition, correctly returning an empty list.
Input array contains all identical values	The strict inequality check ensures no element is considered a peak since it can never be strictly greater than its neighbors.
Input array contains a 'plateau' of identical values	The 'strictly greater' requirement correctly prevents any element on the plateau from being identified as a peak.
The overall maximum value in the array is at the first or last position	The solution correctly ignores endpoints as potential peaks by iterating only from the second to the second-to-last element.
The input array contains multiple valid peaks	The solution should correctly identify and collect the indices for all elements that meet the peak definition.
An element has one equal neighbor and one smaller neighbor	The condition that a peak must be strictly greater than both neighbors correctly disqualifies such an element.
Inputs with values at the specified boundaries, such as 1 and 100	The solution's logic is based on relative comparisons, so the absolute magnitude of the numbers does not affect its correctness.

Input array has the minimum allowed length of 3

How to Handle:

The solution correctly checks only the middle element at index 1 as a potential peak.

Input array has no peaks, such as a monotonically increasing or decreasing array

How to Handle:

The loop will complete without finding any elements that satisfy the peak condition, correctly returning an empty list.

Input array contains all identical values

How to Handle:

The strict inequality check ensures no element is considered a peak since it can never be strictly greater than its neighbors.

Input array contains a 'plateau' of identical values

How to Handle:

The 'strictly greater' requirement correctly prevents any element on the plateau from being identified as a peak.

The overall maximum value in the array is at the first or last position

How to Handle:

The solution correctly ignores endpoints as potential peaks by iterating only from the second to the second-to-last element.

The input array contains multiple valid peaks

How to Handle:

The solution should correctly identify and collect the indices for all elements that meet the peak definition.

An element has one equal neighbor and one smaller neighbor

How to Handle:

The condition that a peak must be strictly greater than both neighbors correctly disqualifies such an element.

Inputs with values at the specified boundaries, such as 1 and 100

How to Handle:

The solution's logic is based on relative comparisons, so the absolute magnitude of the numbers does not affect its correctness.