Problem Description

You are given a list of mountain peaks, where each peak is represented by its coordinates [x, y]. Each mountain forms a right-angled isosceles triangle shape with:

• Its base along the x-axis
• A right angle at the peak point (x, y)
• Slopes of 1 and -1 for the ascending and descending sides

A mountain is considered visible if its peak is not located inside or on the border of another mountain.

Your task is to count how many mountains are visible.

For example, if a smaller mountain is completely covered by a larger mountain, the smaller one is not visible. The key insight is that each mountain (x, y) can be represented as an interval on the x-axis from (x - y) to (x + y), where y is the height. A mountain is not visible if its interval is completely contained within another mountain's interval.

The solution converts each mountain peak (x, y) into an interval (x - y, x + y) representing its left and right boundaries on the x-axis. Then it sorts these intervals and checks which mountains remain visible by tracking if their intervals are covered by others. Mountains with duplicate intervals are handled specially - if multiple mountains have the exact same interval, they all overlap perfectly and only need to be counted based on visibility rules.

Intuition

The key observation is that each mountain forms a right-angled isosceles triangle. Since the slopes are 1 and -1, if a mountain has its peak at (x, y), the left base point is at (x - y, 0) and the right base point is at (x + y, 0). This means we can represent each mountain as an interval [x - y, x + y] on the x-axis.

Once we have this interval representation, the problem becomes: given a set of intervals, find how many intervals are not completely contained within another interval. This is a classic interval problem.

To determine which intervals are "dominated" by others, we need a clever sorting strategy. We sort by:

1. Left endpoint in ascending order (smaller left points first)
2. When left endpoints are equal, right endpoint in descending order (larger right points first)

This sorting ensures that if one interval can contain another, the containing interval comes first. As we traverse the sorted intervals, we maintain the maximum right endpoint seen so far. If an interval's right endpoint doesn't extend beyond this maximum, it means this interval is completely contained within a previous one and thus not visible.

There's one special case to handle: when multiple mountains have identical intervals (same [x - y, x + y]), they perfectly overlap. We use a counter to track duplicates - only intervals that appear exactly once can contribute to the visible count, as duplicate intervals represent mountains that completely overlap each other at the same position.

The algorithm efficiently identifies visible mountains by converting the geometric problem into an interval coverage problem, which can be solved in O(n log n) time through sorting and a single pass.

Learn more about Stack, Sorting and Monotonic Stack patterns.

Solution Approach

The implementation follows these steps:

1. Convert mountains to intervals: For each mountain peak (x, y), calculate its interval representation as (x - y, x + y). This gives us the left and right boundaries on the x-axis.

   arr = [(x - y, x + y) for x, y in peaks]

2. Count duplicates: Use a Counter to track how many times each interval appears. This helps identify mountains that perfectly overlap.

   cnt = Counter(arr)

3. Sort intervals strategically: Sort the intervals by left endpoint ascending, and when left endpoints are equal, by right endpoint descending. This ensures larger intervals come before smaller ones when they share the same left endpoint.

   arr.sort(key=lambda x: (x[0], -x[1]))

4. Traverse and track visibility: Initialize variables:

   • ans to count visible mountains
   • cur to track the maximum right endpoint seen so far (initialized to negative infinity)

   For each interval (l, r):

   • If r <= cur, this interval is completely contained within a previous interval, so skip it
   • Otherwise, update cur = r as we've found an interval that extends further right
   • If this interval appears only once (cnt[(l, r)] == 1), increment the answer

   ans, cur = 0, -inf
   for l, r in arr:
       if r <= cur:
           continue
       cur = r
       if cnt[(l, r)] == 1:
           ans += 1

The algorithm works because:

• The sorting ensures we process potentially containing intervals before contained ones
• By tracking the maximum right endpoint, we can quickly determine if an interval is covered
• The duplicate check ensures mountains with identical intervals don't all get counted as visible

Time complexity: O(n log n) for sorting, where n is the number of mountains. Space complexity: O(n) for storing the intervals and counter.

Example Walkthrough

Let's walk through a small example with peaks: [[2,2], [6,3], [5,4]]

Step 1: Convert mountains to intervals

• Peak (2,2): interval = (2-2, 2+2) = (0, 4)
• Peak (6,3): interval = (6-3, 6+3) = (3, 9)
• Peak (5,4): interval = (5-4, 5+4) = (1, 9)

So arr = [(0,4), (3,9), (1,9)]

Step 2: Count duplicates cnt = {(0,4): 1, (3,9): 1, (1,9): 1} - each interval appears once

Step 3: Sort intervals Sort by left endpoint ascending, then right endpoint descending:

• (0,4) - left=0
• (1,9) - left=1
• (3,9) - left=3

Sorted: arr = [(0,4), (1,9), (3,9)]

Step 4: Traverse and track visibility

• Initialize: ans = 0, cur = -inf

Process (0,4):

• 4 > -inf, so not contained
• Update cur = 4
• cnt[(0,4)] = 1, so ans = 1

Process (1,9):

• 9 > 4, so not contained
• Update cur = 9
• cnt[(1,9)] = 1, so ans = 2

Process (3,9):

• 9 <= 9, so this interval is contained (doesn't extend beyond current max)
• Skip it, don't increment ans

Result: 2 visible mountains

The mountains at peaks (2,2) and (5,4) are visible. The mountain at (6,3) is completely contained within the mountain at (5,4) since its interval (3,9) doesn't extend beyond the interval (1,9).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation. Breaking down the algorithm:

• Converting peaks to intervals (x - y, x + y) takes O(n) time
• Creating a Counter from the intervals takes O(n) time
• Sorting the array of intervals takes O(n × log n) time
• The final loop iterates through all intervals once, taking O(n) time

Since sorting is the most expensive operation, the overall time complexity is O(n × log n), where n is the number of mountains.

Space Complexity: O(n)

The space complexity analysis:

• The arr list stores n transformed intervals, requiring O(n) space
• The Counter object cnt stores at most n unique interval entries, requiring O(n) space
• The sorting operation may use O(log n) to O(n) additional space depending on the implementation
• Other variables (ans, cur) use O(1) space

Therefore, the total space complexity is O(n), where n is the number of mountains.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Duplicate Mountains

One of the most common mistakes is not properly handling mountains that have identical intervals. When multiple mountains have the exact same base interval (x-y, x+y), they completely overlap each other, making all of them "invisible" according to the problem's visibility rules.

Incorrect approach:

def visibleMountains(self, peaks: List[List[int]]) -> int:
    intervals = [(x - y, x + y) for x, y in peaks]
    intervals.sort(key=lambda interval: (interval[0], -interval[1]))
  
    visible_count = 0
    max_right_seen = float('-inf')
  
    for left, right in intervals:
        if right <= max_right_seen:
            continue
        max_right_seen = right
        visible_count += 1  # Wrong! Counts duplicates as visible
  
    return visible_count

Why it fails: If peaks [2, 2] and [2, 2] both exist, they create identical intervals (0, 4). The incorrect code would count one as visible, but since they perfectly overlap, neither should be counted.

Solution: Use a Counter to track duplicate intervals and only count intervals that appear exactly once:

interval_counts = Counter(intervals)
# ... in the loop:
if interval_counts[(left, right)] == 1:
    visible_count += 1

2. Incorrect Sorting Strategy

Another pitfall is using the wrong sorting key, which can lead to processing smaller mountains before larger ones that share the same left endpoint.

Incorrect approach:

intervals.sort()  # Default sort: by left, then by right ascending

Why it fails: With default sorting, an interval like (0, 3) would come before (0, 5). When we process (0, 3) first, we'd mark it as visible and update max_right_seen = 3. Then when processing (0, 5), we'd also mark it as visible. However, (0, 3) should actually be hidden by (0, 5).

Solution: Sort by left endpoint ascending, but right endpoint descending when left endpoints are equal:

intervals.sort(key=lambda interval: (interval[0], -interval[1]))

This ensures that when two intervals share the same left endpoint, the one with the larger right endpoint (the bigger mountain) is processed first.

3. Not Removing Duplicates from the Sorted List

Some might try to remove duplicates after sorting but before the visibility check, which can lead to inefficient code or logical errors.

Problematic approach:

intervals = list(set(intervals))  # Removes duplicates but loses count information
intervals.sort(key=lambda interval: (interval[0], -interval[1]))

Why it's problematic: While this removes duplicates, you lose the information about which mountains were duplicates, making it impossible to correctly determine that none of the duplicate mountains should be counted as visible.

Better solution: Keep all intervals in the sorted list but use the Counter to track which ones are duplicates, allowing you to process each interval exactly once while knowing whether it had duplicates.