Problem Description

There are n mountains in a row, and each mountain has a height. You are given an integer array height where height[i] represents the height of mountain i, and an integer threshold.

A mountain is called stable if the mountain just before it (if it exists) has a height strictly greater than threshold. Note that mountain 0 is not stable.

Return an array containing the indices of all stable mountains in any order.

Intuition

To determine which mountains are stable based on the given condition, we focus on the relative heights of the mountains and the provided threshold value.

The main observation is that a mountain at index i is considered stable if the mountain immediately before it at index i-1 is taller than the threshold. Notably, the mountain at index 0 cannot be stable because there is no preceding mountain to compare. Consequently, we only need to check mountains from index 1 onward.

The solution involves iterating over the list of heights starting from index 1. For each mountain, we check if the height of the previous mountain (at index i-1) surpasses the threshold. If true, we record the current index i as a stable mountain. By simply traversing through the list once, we efficiently identify and collect the indices of all stable mountains.

Solution Approach

The solution makes use of a straightforward traversal of the height array. Here is how the approach is implemented:

1. Loop Initialization:

   • We begin by iterating from index 1 up to len(height) - 1 since mountain 0 does not have a preceding mountain to consider for stability.

2. Check Stability Condition:

   • For each mountain at index i, we check if the height of the preceding mountain height[i - 1] is greater than the specified threshold.
   • If this condition is met, the mountain at index i is stable.

3. Collect Stable Mountain Indices:

   • Whenever a mountain is identified as stable, we append its index i to a result list.

4. Return Result:

   • After completing the iteration, we return the list of indices representing stable mountains.

This approach is implemented in the following code:

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]

The code employs a list comprehension to construct the output list dynamically, resulting in a concise implementation. By traversing the list only once, the algorithm achieves linear time complexity, making it efficient to handle large datasets.

Example Walkthrough

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

Input:

• height = [10, 5, 8, 7]
• threshold = 6

Objective:

Identify the indices of stable mountains based on the given threshold.

Steps:

1. Initialization:

   • We start iterating from index 1, because mountain 0 has no preceding mountain.

2. Iterate and Check Stability:

   • Index 1:

     • Calculate condition: height[0] (10) > threshold (6)
     • This is true. So, the mountain at index 1 is stable.
     • Add index 1 to the results.

   • Index 2:

     • Calculate condition: height[1] (5) > threshold (6)
     • This is false. The mountain at index 2 is not stable.
     • Do not add index 2 to the results.

   • Index 3:

     • Calculate condition: height[2] (8) > threshold (6)
     • This is true. So, the mountain at index 3 is stable.
     • Add index 3 to the results.

3. Result Collection:

   • Our resulting list of stable mountain indices is [1, 3].

Output:

• Indices of stable mountains: [1, 3]

This simple traversal efficiently determines which mountains meet the stability condition relative to their predecessors, offering a clear understanding of how the algorithm processes the input data.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array height. This is because the solution iterates through the list once with a list comprehension, evaluating height[i - 1] > threshold for each element beyond the first.

The space complexity of the code is O(n) because the list comprehension generates a new list, which, in the worst case, could store all indices except the first one. Ignoring the space consumption of the result array itself, an auxiliary space complexity can be considered as O(1).

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