Finding the Number of Visible Mountains

🌍 The Why?

Event Timeline Visibility:

• Think of mountains as tasks, events, or ads that want to be seen. Only those not completely covered by others are visible.
• Used in calendars, UI timelines, animation layering, and video editing tracks.

Geospatial Analysis / 3D Modeling:

• In rendering or simulation, visibility computation like this is used to determine what’s in view for e.g in gaming.

Ad Impression Systems:

• Only those ads (mountains) whose core message (peak) isn't hidden by bigger ad spaces other intervals get counted.

This algorithm is important because it teaches us how to find what truly stands out when things overlap. Just like tall mountains can hide smaller ones, some events or items get overshadowed in real life too on maps, timelines, or screens.

By sorting and scanning smartly, we figure out what’s actually visible. It’s fast, elegant, and applies to everything from calendar events to ad placements and 3D graphics.

The Situation:

You are given a list of mountains defined by their peaks on a 2D grid. Each mountain forms a right-angled isosceles triangle with its base on the x-axis.

Isosceles triangle: In geometry, an isosceles triangle is a triangle that has two sides of equal length and two angles of equal measure.

The goal is to determine how many of these mountains are visible meaning their peaks do not lie inside or on the side of any other mountain.

Even if a mountain has a unique interval, it should only be considered visible if its peak lies outside all previously seen intervals.

The Question:

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.

The Task:

Efficiently compute the number of visible mountains from the given list, even if there are up to 100,000 mountains. Ensure performance is optimised and accounts for overlapping and identical mountains.

Action:

What can we do to solve this?

1. Let's see how the mountain range expands.

🔍 Interpret the Mountain

Input: peaks = [[2,2],[6,3],[5,4]]

Each mountain is a triangle with its peak at [x, y].

The base spans from:

• start = x−y
• end = x+y

So we can represent each mountain as an interval [start, end]

Input: peaks = [[1,3],[1,3]]

2. Visibility Criteria

A mountain is not visible if any other mountain's interval fully covers it, including it's peak. That means:

1. If interval A is completely inside interval B, and two are not identical then A is not visible
2. if two intervals are exactly the same, they both obscure each other's peak so neither is visible.

3. Steps to Solve:

• Convert each peak [x, y] to an interval representing the mountains's base:

interval  = [x -y, x + y]

1. Sort all intervals
2. First by start in ascending order.
3. Then end in descending order to prioritise wider mountains when start points are equal
4. Count visible mountains by iterating through the sorted intervals:
5. use map to count occurrences of each interval
6. skip intervals that occur more than once as they completely overlap
7. for unique intervals, only count it as visible if it's end is greater than maxEndSeenSoFar

function countVisibleMountains(peaks):
  intervals = []

  // Step 1: Convert each peak to interval
  for each [x, y] in peaks:
    start = x - y
    end = x + y
    intervals.append([start, end])
   

  // Step 2: Count frequency of each interval
  freqMap = {}
  for each interval in intervals:
    key = (start, end) as string or tuple
    increment freqMap[key] by 1

  // Step 3: Sort intervals by start ASC, then end DESC
  sort intervals by:
    start ascending
    end descending

  // Step 4: Count visible mountains
  visibleCount = 0
  maxEndSeen = -infinity

  for each interval in intervals:
    key = (start, end) as string 
    if freqMap[key] > 1:
      continue // skip duplicate overlapping intervals
    if  maxEndSeen < end:
      visibleCount += 1
    maxEndSeen = end
   
  return visibleCount

Actual Code:

Input: peaks = [[2,2],[6,3],[5,4]]

var visibleMountains = function(peaks) {
    const intervals = peaks.map(([x, y]) => [x - y, x + y]);
    

    // Count duplicates
    let map = new Map();
    for (let [x, y] of intervals) {
        let key = x + ',' + y;
        map.set(key, (map.get(key) || 0) + 1);
    }
    

// if start is equal sort by end point 
// else sort by start point ascending, 
    intervals.sort((a, b) => {
        if (a[0] === b[0]) {
            return b[1] - a[1];
        }
        return a[0] - b[0];
    });

    let visible = 0;
    let maxEndSeenSoFar = -Infinity;
    
    for (let [start, end] of intervals) {
        let key = start + ',' + end;
        
        // Update maxEndSeenSoFar regardless of duplicates
        if (end > maxEndSeenSoFar) {
            // Only count as visible if not a duplicate
            if (map.get(key) === 1) {
                visible++;
            }
            maxEndSeenSoFar = end;
        }
    }
    return visible;
};

The Result:

Space Complexity: O(N)

1. O(N) space for the intervals array
2. O(N) space for the frequency map
3. Total: O(N)

Time Complexity: O(N log N)

1. O(N) time to convert peaks to intervals
2. O(N) time to build the frequency map
3. O(N log N) time for sorting the intervals
4. O(N) time for the final pass to count visible mountains
5. Total: O(N log N)

The sorting step creates the O(N log N) bottleneck in this algorithm, which is unavoidable since we need to process the mountains in a specific order.

The rest of the operations are all linear time.

#leetcode #intervals #google