Finding the Number of Visible Mountains

Finding the Number of Visible Mountains

1. What is this problem about?

The Finding the Number of Visible Mountains interview question is a 2D geometry and interval problem. Each mountain is represented by its peak $(x, y)$ and extends downwards at 45-degree angles to the X-axis. A mountain is "visible" if it is not completely covered by any other mountain. If two mountains are identical, both are considered invisible (or only one is counted, depending on the variant).

2. Why is this asked in interviews?

Companies like Salesforce and Google ask the Finding the Number of Visible Mountains coding problem to see if a candidate can transform 2D shapes into 1D intervals. It evaluations your ability to use Monotonic Stacks or Sorting to handle overlapping ranges. It’s a test of spatial reasoning and geometric simplification.

3. Algorithmic pattern used

This problem follows the Interval Covering pattern.

1. Transformation: A mountain with peak $(x, y)$ covers the interval $[x-y, x+y]$ on the X-axis.
2. The Property: Mountain A covers Mountain B if $start_A \leq start_B$ and $end_A \geq end_B$.
3. Sorting: Sort the mountains by their start points (ascending) and then by their end points (descending).
4. Greedy Scan: Iterate through the sorted mountains. Keep track of the furthest right_boundary seen so far. A mountain is potentially visible if its end point is greater than the current right_boundary.
5. Duplicate Check: Handle the edge case where two mountains are identical.

4. Example explanation

Mountain 1: peak (2, 2) -> Range [0, 4]. Mountain 2: peak (3, 1) -> Range [2, 4].

• Sort: [0, 4], [2, 4].
• First mountain [0, 4] is visible. max_right = 4.
• Second mountain [2, 4] has $start \geq 0$ and $end \leq 4$. It is completely covered. Result: 1 visible mountain.

5. Common mistakes candidates make

• 2D Complexity: Trying to check for overlap using triangle intersection math instead of simplifying to 1D intervals.
• Incorrect Sorting: Forgetting to sort by end point descending for the same start point, which is crucial for the greedy "cover" check.
• Ignoring Identical Mountains: Failing to handle the case where two mountains overlap perfectly.

6. Interview preparation tip

Whenever you see "shapes" that cover other "shapes," try to find a 1D projection. Converting 2D geometry into an Interval interview pattern problem is one of the most effective ways to reduce complexity from $O(N^2)$ to $O(N \log N)$.