#3285

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Find Indices of Stable Mountains

Find the indices of stable mountains in an array of mountain heights based on a threshold.

Problem Statement

Given an array height of size n, each element represents the height of a mountain. A stable mountain is one where the previous mountain has a height strictly greater than the given threshold. The first mountain (index 0) is not stable by definition.

Return an array containing the indices of all stable mountains. If no stable mountain exists, return an empty array.

Examples

Example 1

Input: height = [1,2,3,4,5], threshold = 2

Output: [3,4]

Example 2

Input: height = [10,1,10,1,10], threshold = 3

Output: [1,3]

Example details omitted.

Example 3

Input: height = [10,1,10,1,10], threshold = 10

Output: []

Example details omitted.

Constraints

2 <= n == height.length <= 100
1 <= height[i] <= 100
1 <= threshold <= 100

Solution Approach

Iterate and Compare

Iterate through the height array starting from the second element. For each mountain, check if the previous one exceeds the threshold. If true, add the current index to the result array.

Array-Driven Strategy

The problem is best approached by scanning through the array once, utilizing the threshold condition to filter stable mountains. The result will directly correspond to indices of valid elements.

Optimize Space Complexity

To minimize space usage, maintain a list of stable mountain indices without using additional arrays for temporary storage. This ensures that space complexity is kept to O(n).

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because the solution involves a single pass through the array. The space complexity is O(n) due to storing the stable mountain indices in a result array.

What Interviewers Usually Probe

Look for a clear understanding of array manipulation.
Expect direct application of array-driven solution strategies.
Evaluate for an efficient implementation regarding space and time.

Common Pitfalls or Variants

Common pitfalls

Failing to check the condition for the first mountain.
Incorrectly handling the threshold comparison, especially boundary cases.
Not considering edge cases like when no stable mountain exists.

Follow-up variants

Change the threshold dynamically within the array processing.
Add additional constraints like maximum height or larger input sizes.
Use a more complex comparison for stability, such as a moving threshold.

FAQ

What is a stable mountain in this problem?

A stable mountain is one where the previous mountain has a height strictly greater than the given threshold.

How do you handle the first mountain in the array?

The first mountain (index 0) is not considered stable, as there is no previous mountain to compare it with.

What happens if no stable mountains exist?

If no stable mountains are found, return an empty array.

How can I optimize the space complexity for this problem?

Space complexity can be optimized by directly storing the indices of stable mountains in a result array without any temporary data structures.

What is the time complexity of this solution?

The time complexity is O(n) because the solution only requires a single pass through the array.

terminal

Solution

Solution 1: Traversal

We directly traverse the mountains starting from index $1$. If the height of the mountain to its left is greater than $threshold$, we add its index to the result array.

1

2

3

class Solution:
    def stableMountains(self, height: List[int], threshold: int) -> List[int]:
        return [i for i in range(1, len(height)) if height[i - 1] > threshold]

Continue Practicing

#3286 find a safe walk through a grid #3283 maximum number of moves to kill all pawns #3287 find the maximum sequence value of array