Is Finding the Number of Visible Mountains easy or hard?

The problem is rated Medium because the main challenge is recognizing the interval transformation from (x, y) peaks to [x − y, x + y] ranges. Once modeled as an interval coverage problem, sorting and scanning solves it efficiently in O(n log n) time.

Finding the Number of Visible Mountains Python/Java solution

The implementation converts peaks into intervals, sorts them by (left asc, right desc), then iterates while maintaining the largest right boundary seen. Each interval with a strictly larger right endpoint becomes visible unless it is a duplicate interval. The same logic works in Python, Java, C++, and Go.

How to solve Finding the Number of Visible Mountains in O(n)?

A strict O(n) solution is generally not possible because the mountains must be ordered by their interval boundaries to detect coverage. Sorting the intervals by left and right endpoints enables a single pass visibility check. The resulting algorithm runs in O(n log n) time followed by an O(n) traversal.

What is the best approach for Finding the Number of Visible Mountains?

The best approach converts each mountain into an interval [x - y, x + y], sorts intervals by left ascending and right descending, then scans once while tracking the maximum right boundary. If the current interval's right edge is less than or equal to the maximum seen, it is covered and not visible. This interval sorting + traversal method runs in O(n log n) time and O(1) extra space.

Is Finding the Number of Visible Mountains asked at Google/Amazon/Meta?

Problems involving interval coverage, skyline views, and visibility frequently appear in interviews at companies like Google, Amazon, and Meta. This specific problem tests interval transformation, sorting strategy, and reasoning about overlapping ranges, which are common interview patterns.

What data structure is used in Finding the Number of Visible Mountains?

The main technique uses sorted arrays of intervals and optionally a monotonic stack. Sorting organizes mountains by their left boundary, while a running maximum or stack structure helps detect when an interval is completely covered by another.

What is the time complexity of Finding the Number of Visible Mountains?

The optimal solution runs in O(n log n) time due to sorting the intervals derived from mountain peaks. After sorting, a single linear traversal determines visibility, which adds O(n). Space complexity is O(1) or O(n) depending on whether intervals are stored separately.

Description Hints 3 Solution Video 9:57

2345. Finding the Number of Visible Mountains

Medium37.3% acceptance2 companiesPremium elsewhere, free here

You are given a 0-indexed 2D integer array peaks where peaks[i] = [x_i, y_i] states that mountain i has a peak at coordinates (x_i, y_i). 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 <= 10⁵
peaks[i].length == 2
1 <= x_i, y_i <= 10⁵

Asked at 2 companies

Salesforce

Google

Topics

Hints open one at a time

Hint 1

How can we efficiently find for each mountain the relevant mountains to compare itself against to check whether or not it would be visible?

Hint 2

Do you notice a pattern after sorting the peaks by their x-coordinates?

Hint 3

After sorting, process the peaks sequentially and use a monotonic stack to store currently visible mountains.

9:57

Still stuck?Read the written solution, or watch a walkthrough.

Open solution