Find Indices of Stable Mountains — Problem & Solution
Find Indices of Stable Mountains solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find Indices of Stable Mountains is an easy coding problem on arrays, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n mountains in a row; mountain i has height height[i]. A mountain is stable when the mountain immediately before it is strictly taller than threshold. Mountain 0 has nothing before it, so it is never stable.
Return the indices of all stable mountains in increasing order (an empty array if there are none).
Example 1
Input: height = [1,2,3,4,5], threshold = 2
Output: [3,4]
Explanation: Mountain 3 follows height 3 > 2 and mountain 4 follows height 4 > 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: []
Explanation: No height is strictly greater than 10.
Constraints
2 <= n == height.length <= 1001 <= height[i] <= 1001 <= threshold <= 100
Hints for Find Indices of Stable Mountains
Hint 1
Stability of mountain
idepends only onheight[i - 1]— not on its own height.Hint 2
Loop
ifrom1ton - 1and keepiwheneverheight[i - 1] > threshold; the loop order already gives increasing indices.
How to solve Find Indices of Stable Mountains
Each mountain's stability is a single comparison on its left neighbour, so one pass collects the answer, already in increasing order.
Approach
- Start with an empty list.
- For
i = 1 .. n - 1, appendiifheight[i - 1] > threshold. - Return the list.
Why it works
The definition is checked literally for every index that can be stable, and indices are visited in increasing order.
Complexity
- Time —
O(n) - Space —
O(1) besides the output
Pitfalls
- The comparison is strict: a neighbour exactly equal to
thresholddoes not make a mountain stable. - Return the index of the mountain after the tall one, not the tall one itself.
Reference solution
Python
from typing import List
def stableMountains(height: List[int], threshold: int) -> List[int]:
return [i for i in range(1, len(height)) if height[i - 1] > threshold]Java
public static int[] stableMountains(int[] height, int threshold) {
List<Integer> out = new ArrayList<>();
for (int i = 1; i < height.length; i++) if (height[i - 1] > threshold) out.add(i);
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> stableMountains(vector<int>& height, int threshold) {
vector<int> out;
for (size_t i = 1; i < height.size(); i++) if (height[i - 1] > threshold) out.push_back((int) i);
return out;
}JavaScript
var stableMountains = function(height, threshold) {
var out = [];
for (var i = 1; i < height.length; i++) if (height[i - 1] > threshold) out.push(i);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays