Finding The Number Of Visible Mountains
01 · Problem
You are given a 2D integer array peaks where peaks[i] = [x_i, y_i] is the top of mountain i. Every mountain is a right-angled isosceles triangle standing on the x-axis: its sides slope down at 45 degrees on both sides, so its base runs from (x_i - y_i, 0) to (x_i + y_i, 0).
A mountain is visible if its peak does not lie inside another mountain or on the border of another mountain. In particular, if two or more mountains are identical (same peak), they hide each other and none of them is visible.
Return the number of visible mountains.
02 · Examples
peaks = [[2,4],[5,2],[9,1]]
3
At x = 5 the first mountain is only 1 high, below the peak [5,2], so that peak is visible. [9,1] spans 8..10 and touches no other mountain above the ground. All 3 peaks are visible.
peaks = [[4,2],[4,2],[6,5]]
1
The two [4,2] mountains are identical, so they hide each other, and both also lie inside [6,5] (base 1..11). Only [6,5] is visible.
peaks = [[1,1],[4,2],[4,1]]
2
[4,1] lies inside [4,2]. [1,1] (base 0..2) and [4,2] (base 2..6) only touch at the ground, so both are visible.
03 · Constraints
- 011 <= peaks.length <= 105
- 02peaks[i].length == 2
- 031 <= x_i, y_i <= 105
04 · Optimal complexity
- Time
- O(n log n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.