Find Indices of Stable Mountains
EasyPrompt
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] == 3is greater thanthreshold == 2. - Mountain 4 is stable because
height[3] == 4is greater thanthreshold == 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 <= 1001 <= height[i] <= 1001 <= 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
- Initialize an empty list,
result, to store the indices of stable mountains. - Iterate through the
heightarray with an indexifrom1ton-1. - Inside the loop, check if the height of the preceding mountain,
height[i-1], is strictly greater thanthreshold. - If the condition is true, add the current index
ito theresultlist. - After the loop finishes, return the
resultlist.
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.
This approach directly translates the problem definition into code. We iterate through each mountain from the very first one (index 0) to the last, and for each mountain, we check if it satisfies the conditions to be considered 'stable'.
Algorithm
- Initialize an empty list,
result, to store the indices of stable mountains. - Iterate through the
heightarray with an indexifrom0ton-1, wherenis the length of the array. - Inside the loop, check if
i > 0to ensure a preceding mountain exists. - If
i > 0, then check ifheight[i-1]is strictly greater thanthreshold. - If both conditions are met, add the current index
ito theresultlist. - After the loop finishes, return the
resultlist.
Walkthrough
The algorithm involves a single loop that traverses the entire height array. For each mountain at index i, we perform two checks:
- Existence of a preceding mountain: We check if
i > 0. This is crucial because mountain 0 has no preceding mountain and is explicitly defined as not stable. - Height of the preceding mountain: If a preceding mountain exists (at index
i-1), we check if its height,height[i-1], is strictly greater than the giventhreshold.
If both conditions are true, the index i is added to a result list. This list is then returned after the loop completes.
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; for (int i = 0; i < n; i++) { // Check if a preceding mountain exists and its height is > threshold if (i > 0 && height[i - 1] > threshold) { stableIndices.add(i); } } return stableIndices; }}Complexity
Time
O(n), where n is the number of mountains. We iterate through the entire array once.
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) to store the result list.
Trade-offs
Pros
Very simple to understand as it directly models the problem statement.
Correct and handles all edge cases.
Cons
Slightly inefficient as it starts the loop from index 0 and performs a check (
i > 0) in every iteration, even though we know mountain 0 can never be stable.
Solutions
Solution
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; }}class Solution {public: vector<int> stableMountains(vector<int> &height, int threshold) { vector<int> ans; for (int i = 1; i < height.size(); ++i) { if (height[i - 1] > threshold) { ans.push_back(i); } } return ans; }};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]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.