Finding the Number of Visible Mountains

Published: Jan 12, 2023

Problem Description

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.

Constraints:

• 1 <= peaks.length <= 10**5
• peaks[i].length == 2
• 1 <= x[i], y[i] <= 10**5

https://leetcode.com/problems/finding-the-number-of-visible-mountains/

Examples

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.

How to Solve

From the description that the triangle is a right-angled isosceles triangle, two slopes are: y = x + b and y = -x + b where b is a y intercept. We can easily find two y intercepts as y - x and y + x. Positions of triangles are separated, partially overlap, or included. For the first step, sort y intercept pairs: (y - x, y + x) in a descending order, which means the triangles are arranged from left most to right most. Then, check one by one whether the upper y intercept is greater than the current max value. However, if the peaks overlap, those should not be counted. Update the max value if it is a bigger y intercept.

Solution

class FindingTheNumberOfVisibleMountains {
public:
    int visibleMountains(vector<vector<int>>& peaks) {
        for (int i = 0; i < peaks.size(); ++i) {
            int x = peaks[i][0], y = peaks[i][1];
            peaks[i][0] = y - x, peaks[i][1] = y + x;
        }
        sort(peaks.begin(), peaks.end(),
            [](const vector<int> &a, const vector<int> &b) -> bool {
                return a[0] == b[0] ? a[1] > b[1] : a[0] > b[0];
            });
        int result = 0, max_v = 0, n = peaks.size();
        for (int i = 0; i < n; ++i) {
            if (peaks[i][1] > max_v) {
                if (i == n - 1 || peaks[i][0] != peaks[i + 1][0] || peaks[i][1] != peaks[i + 1][1]) {
                    result++;
                }
                max_v = peaks[i][1];
            }
        }
        return result;
    }
};

class FindingTheNumberOfVisibleMountains:
    def visibleMountains(self, peaks: List[List[int]]) -> int:
        peaks = [(y - x, y + x) for x, y in peaks]
        peaks.sort(reverse=True)
        n, max_v, result = len(peaks), 0, 0
        for i in range(n):
            if  peaks[i][1] > max_v:
                if i == n - 1 or peaks[i] != peaks[i + 1]:
                    result += 1
                max_v = peaks[i][1]
        return result

Complexities

• Time: O(n * log(n))
• Space: O(1)