Finding the Number of Visible Mountains - Solution & Explanation
Problem Statement
You are given a 0-indexed 2D integer array peaks where peaks[i] = [xi, yi] states that mountain i has a peak at coordinates (xi, yi). A mountain can be described as a right-angled isosceles triangle, with its base along the x-axis and a right angle at its peak. More formally, the gradients of ascending and descending the mountain are 1 and -1 respectively.
A mountain is considered visible if its peak does not lie within another mountain (including the border of other mountains).
Return the number of visible mountains.
Example 1:
Input: peaks = [[2,2],[6,3],[5,4]] Output: 2 Explanation: The diagram above shows the mountains. - Mountain 0 is visible since its peak does not lie within another mountain or its sides. - Mountain 1 is not visible since its peak lies within the side of mountain 2. - Mountain 2 is visible since its peak does not lie within another mountain or its sides. There are 2 mountains that are visible.
Example 2:
Input: peaks = [[1,3],[1,3]] Output: 0 Explanation: The diagram above shows the mountains (they completely overlap). Both mountains are not visible since their peaks lie within each other.
Constraints:
1 <= peaks.length <= 105peaks[i].length == 21 <= xi, yi <= 105
Approach Overview
Problem Overview: Each mountain is defined by a peak (x, y). The mountain spans from x - y to x + y. A mountain is visible only if no other mountain completely covers this interval. The task is to count how many mountains remain visible after considering all overlaps.
Approach 1: Brute Force Interval Comparison (O(nĀ²) time, O(1) space)
Convert every mountain into an interval [left, right] where left = x - y and right = x + y. For each mountain, iterate through all others and check whether another interval fully covers it. If an interval [l2, r2] satisfies l2 ā¤ l1 and r2 ā„ r1, the first mountain is hidden. Count intervals that are never covered. This method is straightforward but slow for large inputs because every pair of mountains must be compared.
Approach 2: Interval Sorting + Traversal (O(n log n) time, O(1) extra space)
Transform mountains into intervals and sort them by left ascending and right descending. Sorting this way ensures that wider mountains appear before smaller ones starting at the same position. Traverse the sorted list while tracking the maximum right boundary seen so far. If the current interval's right is less than or equal to this maximum, it is fully covered and therefore invisible. Otherwise, it becomes a new visible candidate and updates the maximum boundary.
Duplicate intervals require special handling. When two mountains produce identical [left, right] intervals, neither should count as visible because each hides the other. Detect duplicates during traversal and exclude them from the final count. This approach works because sorting guarantees that once an interval is covered, all later intervals starting further right cannot reveal it.
Approach 3: Monotonic Stack over Sorted Intervals (O(n log n) time, O(n) space)
After sorting intervals by left, maintain a monotonic stack storing intervals with strictly increasing right boundaries. When a new interval appears, pop intervals that are fully covered by it. If the new interval itself is covered by the top of the stack, skip it. The stack always represents visible candidates. This pattern resembles skyline-style problems and uses properties of a stack combined with sorted arrays.
Recommended for interviews: The interval sorting + traversal solution is the expected answer. It reduces the problem to interval coverage detection after sorting and runs in O(n log n) time. Mentioning the brute force approach first shows you understand the visibility definition, while the optimized traversal demonstrates practical problem-solving and familiarity with interval techniques.
Solution
We first convert each mountain (x, y) into a horizontal interval (x - y, x + y), then sort the intervals by left endpoint in ascending order and right endpoint in descending order.
Next, we initialize the right endpoint of the current interval as -infty. We traverse each mountain. If the right endpoint of the current mountain is less than or equal to the right endpoint of the current interval, we skip this mountain. Otherwise, we update the right endpoint of the current interval to the right endpoint of the current mountain. If the interval of the current mountain appears only once, we increment the answer.
Finally, we return the answer.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of mountains.
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Interval Comparison | O(nĀ²) | O(1) | Small inputs or when demonstrating the basic visibility definition |
| Interval Sorting + Traversal | O(n log n) | O(1) | General optimal solution for detecting covered intervals |
| Sorted Intervals with Monotonic Stack | O(n log n) | O(n) | Useful when modeling visibility problems with stack-based skyline logic |
Video Solution
Leetcode 2345[Meta, Amazon]. Finding the Number of Visible Mountains - intervals merge type ā¢ Code-Yao ā¢ 1,780 views views
Watch 5 more video solutions āFrequently Asked Questions
Is Finding the Number of Visible Mountains easy or hard?
Finding the Number of Visible Mountains Python/Java solution
How to solve Finding the Number of Visible Mountains in O(n)?
What is the best approach for Finding the Number of Visible Mountains?
Is Finding the Number of Visible Mountains asked at Google/Amazon/Meta?
What data structure is used in Finding the Number of Visible Mountains?
What is the time complexity of Finding the Number of Visible Mountains?
Ready to solve this problem?
Practice Finding the Number of Visible Mountains with our built-in code editor and test cases.
Practice on FleetCode