LeetCode 2951 - Find the Peaks

LeetCode Problem 2951

Difficulty: 🟢 Easy
Topics: Array, Enumeration

Solution

Problem Understanding

The problem is asking us to identify all the peaks in a given array mountain. A peak is an element that is strictly greater than its immediate neighbors. Importantly, the first and last elements of the array cannot be peaks because they do not have two neighbors.

The input is a zero-indexed array of integers mountain with length between 3 and 100. Each element ranges from 1 to 100. The output should be an array of indices representing the peaks. The order of indices does not matter.

Edge cases to consider include arrays where no elements are peaks (like strictly increasing or decreasing sequences) and arrays with repeated values that prevent elements from being strictly greater than neighbors.

Approaches

The brute-force approach is simple: iterate through the array from the second element to the second-last element and check if each element is strictly greater than its left and right neighbors. If it is, record its index. This approach is correct because it directly follows the definition of a peak. For the given constraints (n <= 100), this solution is efficient.

The optimal approach is essentially the same as the brute-force approach because the input size is small and there is no faster method than checking each internal element. Therefore, the straightforward iteration is both simple and optimal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Iterate through internal elements and check neighbors
Optimal	O(n)	O(n)	Same as brute-force due to small input size

Algorithm Walkthrough

1. Initialize an empty list peaks to store indices of peak elements.
2. Iterate over the array from index 1 to len(mountain) - 2 (inclusive) because first and last elements cannot be peaks.
3. For each element mountain[i], check if it is strictly greater than both mountain[i-1] and mountain[i+1].
4. If it is, append i to peaks.
5. After the loop, return the list peaks.

Why it works: This algorithm checks each internal element exactly once and verifies the condition for a peak. Since the problem definition requires only internal elements and strict inequality, this guarantees that all identified indices are peaks and none are missed.

Python Solution

from typing import List

class Solution:
    def findPeaks(self, mountain: List[int]) -> List[int]:
        peaks = []
        for i in range(1, len(mountain) - 1):
            if mountain[i] > mountain[i - 1] and mountain[i] > mountain[i + 1]:
                peaks.append(i)
        return peaks

In this implementation, we initialize an empty list peaks and iterate over the valid range of indices. We check the peak condition using a simple comparison. If the element qualifies as a peak, we append its index to the list. Finally, we return the list.

Go Solution

func findPeaks(mountain []int) []int {
    peaks := []int{}
    for i := 1; i < len(mountain)-1; i++ {
        if mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1] {
            peaks = append(peaks, i)
        }
    }
    return peaks
}

In Go, we create an empty slice peaks. We iterate from index 1 to len(mountain)-2 and check the peak condition. If the element is a peak, we append its index to the slice using append. The logic mirrors the Python implementation.

Worked Examples

For mountain = [2,4,4]:

i	mountain[i-1]	mountain[i]	mountain[i+1]	Peak?
1	2	4	4	No

Output: []

For mountain = [1,4,3,8,5]:

i	mountain[i-1]	mountain[i]	mountain[i+1]	Peak?
1	1	4	3	Yes
2	4	3	8	No
3	3	8	5	Yes

Output: [1,3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is checked once
Space	O(n)	Space required for storing peak indices

The time complexity is linear in the number of elements because each internal element is visited exactly once. The space complexity is linear in the worst case if every element is a peak.

Test Cases

# Provided examples
assert Solution().findPeaks([2,4,4]) == []  # No peak
assert Solution().findPeaks([1,4,3,8,5]) == [1,3]  # Two peaks

# Boundary tests
assert Solution().findPeaks([1,2,3]) == []  # Last element cannot be peak
assert Solution().findPeaks([3,2,1]) == []  # First element cannot be peak
assert Solution().findPeaks([1,2,1]) == [1]  # Single peak

# Repeated values
assert Solution().findPeaks([1,2,2,1]) == []  # No strictly greater peak
assert Solution().findPeaks([1,3,2,4,2]) == [1,3]  # Multiple peaks

Test	Why
[2,4,4]	No internal element is strictly greater than neighbors
[1,4,3,8,5]	Normal case with multiple peaks
[1,2,3]	Last element cannot be a peak
[3,2,1]	First element cannot be a peak
[1,2,1]	Single peak in the middle
[1,2,2,1]	No strictly greater elements
[1,3,2,4,2]	Multiple peaks

Edge Cases

One important edge case is arrays where all elements are equal, such as [5,5,5,5]. No element will satisfy the strict inequality, so the function correctly returns an empty list. Another edge case is strictly increasing arrays like [1,2,3,4,5] or strictly decreasing arrays like [5,4,3,2,1], where no internal element can be a peak, and the implementation correctly returns []. Finally, arrays of minimal valid length, such as [1,2,1], need to be handled carefully; here the middle element qualifies as a peak, and our loop from 1 to len(mountain)-2 ensures it is checked.