Find Indices of Stable Mountains

EASY

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.

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

Checkout 2 different approaches to solve Find Indices of Stable Mountains. Click on different approaches to view the approach and algorithm in detail.

Optimized Single-Pass Iteration

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

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

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 Analysis

Time Complexity: O(n), where n is the number of mountains. We iterate through the array once, from the second element to the last.Space Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find Indices of Stable Mountains. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find Indices of Stable Mountains

Data Structures:

Array