2345. Finding the Number of Visible Mountains π
Description
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 <= 105
peaks[i].length == 2
1 <= xi, yi <= 105
Solutions
Solution 1: Interval Sorting + Traversal
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|