Scale Engineer

Find Indices of Stable Mountains

Easy
#2916Time: O(n), where n is the number of mountains. We iterate through the array once, from the second element to the last.Space: O(k), where k is the number of stable mountains. In the worst case, k can be up to n-1, making the space complexity O(n) for the output list.
Data structures
Array

Prompt

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.

 

Example 1:

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

Output: [3,4]

Explanation:

  • Mountain 3 is stable because height[2] == 3 is greater than threshold == 2.
  • Mountain 4 is stable because height[3] == 4 is greater than threshold == 2.

Example 2:

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

Output: [1,3]

Example 3:

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

Output: []

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This is the most efficient approach. Recognizing that mountain 0 can never be stable, we can optimize the iteration by starting our check from mountain 1. This eliminates a redundant condition check inside the loop and makes the code slightly cleaner and more direct.

Algorithm

  1. Initialize an empty list, result, to store the indices of stable mountains.
  2. Iterate through the height array with an index i from 1 to n-1.
  3. Inside the loop, check if the height of the preceding mountain, height[i-1], is strictly greater than threshold.
  4. If the condition is true, add the current index i to the result list.
  5. After the loop finishes, return the result list.

Walkthrough

The core idea is to skip checking mountain 0 altogether. We know a mountain i is stable only if the mountain at i-1 exists and its height is above the threshold. This is only possible for i >= 1.

Therefore, we can start our loop directly from i = 1 and iterate up to n-1. For each i, the preceding mountain i-1 is guaranteed to exist. We only need to perform one check: height[i-1] > threshold. If this condition holds, we add i to our result list.

This approach is optimal as it requires visiting each relevant element of the array exactly once.

import java.util.ArrayList;import java.util.List; class Solution {    public List<Integer> findStableMountains(int[] height, int threshold) {        List<Integer> stableIndices = new ArrayList<>();        int n = height.length;        // Start from index 1, as mountain 0 cannot be stable.        for (int i = 1; i < n; i++) {            // Check if the previous mountain's height is greater than the threshold.            if (height[i - 1] > threshold) {                stableIndices.add(i);            }        }        return stableIndices;    }}

Complexity

Time

O(n), where n is the number of mountains. We iterate through the array once, from the second element to the last.

Space

O(k), where k is the number of stable mountains. In the worst case, k can be up to n-1, making the space complexity O(n) for the output list.

Trade-offs

Pros

  • Optimal time and space complexity.

  • Code is clean, concise, and avoids redundant checks.

  • Most direct and efficient implementation.

Cons

  • There are no significant drawbacks to this approach; it is the ideal solution for this problem.

Solutions

class Solution {public  List<Integer> stableMountains(int[] height, int threshold) {    List<Integer> ans = new ArrayList<>();    for (int i = 1; i < height.length; ++i) {      if (height[i - 1] > threshold) {        ans.add(i);      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem