We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Finding the Number of Visible Mountains

Number: 2485

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a list of mountain peaks represented as points (x, y), each mountain is modeled as a right‑angled isosceles triangle with its base on the x‑axis and the right angle at the peak. Its left and right boundaries are given by (x – y) and (x + y) respectively. A mountain is considered visible if its peak does not lie inside or exactly on the border of any other mountain’s triangle. The task is to determine the number of visible mountains.

Key Insights

  • A mountain with peak (x, y) spans an interval [x – y, x + y] on the x‑axis.
  • Mountain i is completely covered by mountain j if and only if (xj – yj) ≤ (xi – yi) and (xi + yi) ≤ (xj + yj). Note that equality counts as “within”.
  • Sorting the mountains by their left boundary (x – y) and then by right boundary (x + y) in descending order lets us “sweep” and check if the current mountain’s right boundary is covered by any previous mountain.
  • When two or more mountains have exactly the same boundaries, each peak lies on the border of the other. In such cases, none of them is visible.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing the transformed intervals and frequency counts.

Solution

We first transform each mountain’s peak (x, y) into an interval [L, R] where L = x – y and R = x + y. Next, we count how many mountains share the exact same (L, R) interval – if more than one mountain has the same interval, then they hide each other.

After this, we sort the unique intervals by L (ascending) and then by R (descending). We then iterate over these sorted intervals while keeping track of the maximum R encountered so far. For a mountain with frequency 1, if its R value is less than or equal to the current maximum R, then its peak is covered by an earlier mountain; otherwise, it is visible. Mountains with duplicates (frequency greater than 1) are automatically marked as hidden.

Key data structures and techniques used:

  • A list of intervals with a frequency count.
  • Sorting to ensure that a mountain that can cover subsequent mountains comes early.
  • A greedy “sweep-line” style update of the maximum R to test coverage.

This method efficiently determines whether each mountain’s peak is “covered” by checking the boundaries.

Code Solutions

# Python Solution
from collections import defaultdict

def visibleMountains(peaks):
    # Convert each peak to interval (L, R) where L = x - y and R = x + y.
    intervals = []
    for x, y in peaks:
        L, R = x - y, x + y
        intervals.append((L, R))
    
    # Count frequency of each (L, R) interval
    freq = defaultdict(int)
    for interval in intervals:
        freq[interval] += 1
        
    # Remove duplicates by creating a list of (L, R, frequency)
    unique_intervals = [(L, R, freq[(L, R)]) for (L, R) in freq]
    # Sort by L ascending, and then by R descending
    unique_intervals.sort(key=lambda x: (x[0], -x[1]))
    
    visible = 0
    max_R = -float('inf')
    for L, R, count in unique_intervals:
        # If there are duplicates, none are visible (they cover each other)
        if count > 1:
            # Even though they are grouped as not visible, update max_R
            max_R = max(max_R, R)
        else:
            # For a mountain with a unique interval, check if it is not covered by a previous mountain.
            if R > max_R:
                visible += 1
                max_R = R
    return visible

# Example usage:
peaks1 = [[2,2],[6,3],[5,4]]
print(visibleMountains(peaks1))  # Expected output: 2

peaks2 = [[1,3],[1,3]]
print(visibleMountains(peaks2))  # Expected output: 0
← Back to All Questions