Problem Description

You are given an array height representing the heights of n mountains arranged in a row, where height[i] is the height of mountain i. You are also given an integer threshold.

A mountain is considered stable if it meets the following condition:

• The mountain immediately before it (to its left) has a height strictly greater than threshold
• Mountain at index 0 can never be stable since there is no mountain before it

Your task is to find all the stable mountains and return an array containing their indices. The indices can be returned in any order.

For example, if height = [10, 1, 5, 3, 8] and threshold = 4:

• Mountain at index 0: Not stable (no mountain before it)
• Mountain at index 1: Stable (mountain before it has height 10, which is > 4)
• Mountain at index 2: Not stable (mountain before it has height 1, which is ≤ 4)
• Mountain at index 3: Stable (mountain before it has height 5, which is > 4)
• Mountain at index 4: Not stable (mountain before it has height 3, which is ≤ 4)

The solution would return [1, 3].

Intuition

The problem asks us to identify which mountains are "stable" based on a simple rule: a mountain is stable if the mountain immediately to its left has a height greater than the threshold.

Since we need to check each mountain's relationship with its immediate left neighbor, we can think of this as a linear scan problem. For each mountain (except the first one at index 0), we just need to look at one thing - the height of the mountain at position i-1.

The key insight is that:

• We start checking from index 1 (since index 0 cannot be stable by definition)
• For each mountain at index i, we only need to check if height[i-1] > threshold
• If this condition is true, then mountain i is stable

This naturally leads to a straightforward solution: iterate through the array starting from index 1, and for each position, check if the previous mountain's height exceeds the threshold. If it does, add the current index to our result list.

The elegance of this approach lies in its simplicity - we don't need any complex data structures or algorithms. A single pass through the array with a simple comparison at each step gives us the answer. This is why the solution can be expressed concisely as a list comprehension: [i for i in range(1, len(height)) if height[i - 1] > threshold].

Solution Approach

The solution implements a direct traversal approach to identify all stable mountains. Here's how the implementation works:

Algorithm: Linear Traversal

We traverse the array of mountain heights starting from index 1 (since mountain at index 0 cannot be stable by definition). For each mountain at position i, we check if the mountain immediately before it (at position i-1) has a height strictly greater than the threshold.

Implementation Details:

1. Starting Point: Begin iteration from index 1 using range(1, len(height)). This skips index 0, which can never be stable.

2. Stability Check: For each index i, check the condition height[i-1] > threshold. This verifies if the previous mountain's height exceeds the threshold.

3. Result Collection: If the condition is satisfied, include index i in the result list.

The Python implementation uses a list comprehension for conciseness:

[i for i in range(1, len(height)) if height[i - 1] > threshold]

This single line of code:

• Iterates through indices from 1 to n-1
• Checks if height[i-1] > threshold for each index i
• Collects all indices where the condition is true

Time Complexity: O(n) where n is the number of mountains, as we make a single pass through the array.

Space Complexity: O(k) where k is the number of stable mountains in the result. In the worst case where all mountains (except the first) are stable, this would be O(n-1).

The beauty of this approach is its straightforward logic - we simply check each mountain's left neighbor against the threshold, making the solution both efficient and easy to understand.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example Input:

• height = [3, 7, 2, 6, 4]
• threshold = 5

Step-by-step Process:

We'll iterate through the array starting from index 1, checking if each mountain's left neighbor has height > 5.

Index 0 (height = 3):

• Skip this mountain as it has no left neighbor
• Cannot be stable by definition

Index 1 (height = 7):

• Check left neighbor: height[0] = 3
• Is 3 > 5? No
• Mountain at index 1 is not stable

Index 2 (height = 2):

• Check left neighbor: height[1] = 7
• Is 7 > 5? Yes
• Mountain at index 2 is stable ✓
• Add index 2 to result: [2]

Index 3 (height = 6):

• Check left neighbor: height[2] = 2
• Is 2 > 5? No
• Mountain at index 3 is not stable

Index 4 (height = 4):

• Check left neighbor: height[3] = 6
• Is 6 > 5? Yes
• Mountain at index 4 is stable ✓
• Add index 4 to result: [2, 4]

Final Result: [2, 4]

Mountains at indices 2 and 4 are stable because their immediate left neighbors (heights 7 and 6 respectively) are both greater than the threshold of 5.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array height. The code iterates through the array once using a list comprehension that goes from index 1 to len(height) - 1. Each iteration performs a constant-time comparison operation (height[i - 1] > threshold), resulting in linear time complexity.

Space Complexity: O(1) (excluding the output array). The algorithm uses only a constant amount of extra space for the loop variable i. If we include the space for the output list, it would be O(k) where k is the number of indices that satisfy the condition, but following the convention stated in the reference answer, we ignore the space consumption of the result array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error: Checking Current Mountain Instead of Previous

A frequent mistake is checking if the current mountain's height exceeds the threshold rather than the previous mountain's height.

Incorrect Implementation:

def stableMountains(self, height: List[int], threshold: int) -> List[int]:
    stable_indices = []
    for i in range(1, len(height)):
        # WRONG: Checking current mountain instead of previous
        if height[i] > threshold:  
            stable_indices.append(i)
    return stable_indices

Why This Fails: The problem requires checking if the mountain immediately before (to the left) has height > threshold. The incorrect code checks the current mountain's height, which completely changes the problem's logic.

Correct Implementation:

def stableMountains(self, height: List[int], threshold: int) -> List[int]:
    stable_indices = []
    for i in range(1, len(height)):
        # CORRECT: Checking previous mountain (i-1)
        if height[i - 1] > threshold:  
            stable_indices.append(i)
    return stable_indices

2. Using Greater Than or Equal (≥) Instead of Strictly Greater Than (>)

Another common error is using >= instead of > when comparing with the threshold.

Incorrect Implementation:

if height[i - 1] >= threshold:  # WRONG: Should be strictly greater

Why This Matters: The problem explicitly states "strictly greater than threshold". If the previous mountain's height equals the threshold, the current mountain should NOT be considered stable.

Example:

• height = [5, 3, 7], threshold = 5
• Mountain at index 1: Previous height is 5
  • With >=: Would incorrectly mark as stable
  • With >: Correctly marked as not stable (5 is not > 5)

3. Including Index 0 in the Iteration

Starting the loop from index 0 and trying to check height[-1] or adding special handling for index 0.

Problematic Approach:

def stableMountains(self, height: List[int], threshold: int) -> List[int]:
    stable_indices = []
    for i in range(len(height)):  # Starts from 0
        if i > 0 and height[i - 1] > threshold:
            stable_indices.append(i)
    return stable_indices

While this works, it adds unnecessary complexity with the i > 0 check. The cleaner approach is to start iteration from index 1, eliminating the need for special case handling.

4. Misunderstanding Which Mountain Gets Added to Result

Some might think we should add the index of the mountain that makes another mountain stable (the tall previous mountain), rather than the stable mountain itself.

Wrong Interpretation:

# WRONG: Adding the index of the mountain that exceeds threshold
for i in range(1, len(height)):
    if height[i - 1] > threshold:
        stable_indices.append(i - 1)  # Wrong index!

Correct Understanding: We add the index i of the mountain that is stable (because its predecessor exceeds the threshold), not the index of the predecessor itself.