3285. Find Indices of Stable Mountains

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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:

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.
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.
Collect Stable Mountain Indices:
- Whenever a mountain is identified as stable, we append its index i to a result list.
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.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

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:

Initialization:
- We start iterating from index 1, because mountain 0 has no preceding mountain.
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.
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

1from typing import List
2
3class Solution:
4    def stableMountains(self, height: List[int], threshold: int) -> List[int]:
5        # List comprehension to iterate over the indices of 'height' starting from 1
6        # Check if the previous mountain's height exceeds the given 'threshold'
7        result = [i for i in range(1, len(height)) if height[i - 1] > threshold]
8      
9        # Return the list of indices where the previous mountain's height exceeds the threshold
10        return result
11

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    /**
6     * This method finds indices in the height array where the previous element
7     * is greater than the given threshold and stores them in a list.
8     *
9     * @param height    an array of integers representing the heights.
10     * @param threshold an integer representing the height threshold.
11     * @return a list of indices where the previous element exceeds the threshold.
12     */
13    public List<Integer> stableMountains(int[] height, int threshold) {
14        List<Integer> ans = new ArrayList<>(); // Initialize the result list
15      
16        // Iterate through the array starting from the second element
17        for (int i = 1; i < height.length; ++i) {
18            // Check if the previous height exceeds the given threshold
19            if (height[i - 1] > threshold) {
20                ans.add(i); // Add the current index to the list
21            }
22        }
23        return ans; // Return the list of indices
24    }
25}
26

1#include <vector>
2
3using namespace std;
4
5class Solution {
6public:
7    vector<int> stableMountains(vector<int>& height, int threshold) {
8        vector<int> ans; // Vector to store indices of "stable" mountains
9        // Iterate through the height vector starting from the second element
10        for (int i = 1; i < height.size(); ++i) {
11            // Check if the previous height is greater than the threshold
12            if (height[i - 1] > threshold) {
13                // Add the current index to the answer vector
14                ans.push_back(i);
15            }
16        }
17        return ans; // Return the indices of stable mountains
18    }
19};
20

1/** 
2 * Function to find indices of mountain peaks that surpass a certain height threshold.
3 * @param height - Array representing the heights of the mountains.
4 * @param threshold - The minimum height a mountain must exceed to be considered stable.
5 * @returns An array of indices where the height of the mountain exceeds the threshold.
6 */
7function stableMountains(height: number[], threshold: number): number[] {
8    const result: number[] = [];
9  
10    // Iterate starting from the second element to compare with the previous one
11    for (let i = 1; i < height.length; ++i) {
12        // If the previous mountain height is greater than the threshold
13        if (height[i - 1] > threshold) {
14            // Store the index of the current element
15            result.push(i);
16        }
17    }
18  
19    // Return the array of indices where conditions are met
20    return result;
21}
22

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.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan: