Solution Explanation: Finding the Number of Visible Mountains

This problem involves determining the number of visible mountains given a list of mountain peaks represented by their coordinates (x, y). A mountain is considered visible if its peak doesn't lie within the boundaries of another mountain.

Approach: Interval Sorting and Traversal

The core idea is to transform the mountain peak coordinates into intervals on the x-axis. Each mountain, represented by coordinates (x, y), can be seen as a horizontal interval spanning from x - y to x + y. A mountain is visible if its interval doesn't completely overlap with any other mountain's interval.

The solution follows these steps:

1. Interval Creation: For each mountain peak (x, y), create an interval (x - y, x + y). This represents the mountain's base along the x-axis.

2. Interval Sorting: Sort the intervals based on their left endpoints (x - y). In case of ties (two mountains have the same left endpoint), sort in descending order based on their right endpoints (x + y). This sorting ensures that we process mountains from left to right, prioritizing mountains with wider bases if they start at the same x-coordinate.

3. Traversal and Visibility Check: Iterate through the sorted intervals. Maintain a variable cur to track the maximum right endpoint encountered so far. For each interval (l, r):

   • If r <= cur, the current mountain is completely covered by a previously encountered mountain and is thus not visible. Skip it.

   • If r > cur, the current mountain's peak extends beyond the previously encountered mountains. It's visible. Update cur to r, making this mountain the current reference.

4. Counting Visible Mountains: Increment a counter for each visible mountain.

5. Return the Count: Finally, return the total count of visible mountains.

Time and Space Complexity Analysis

• Time Complexity: The dominant operation is sorting the intervals, which takes O(n log n) time, where n is the number of mountains. The traversal takes O(n) time. Therefore, the overall time complexity is O(n log n).

• Space Complexity: We create an array of intervals which takes O(n) space. The space used by sorting algorithms depends on the specific implementation, but it typically uses O(log n) or O(n) extra space. Thus, the overall space complexity is O(n).

Code Implementation (Python)

from collections import Counter
 
class Solution:
    def visibleMountains(self, peaks: List[List[int]]) -> int:
        intervals = [(x - y, x + y) for x, y in peaks]
        counts = Counter(intervals)  # Count occurrences of each interval
        intervals.sort(key=lambda x: (x[0], -x[1])) #Sort by left endpoint, then descending by right endpoint.
        visible_count = 0
        max_right = float('-inf')
        for left, right in intervals:
            if right > max_right:
                max_right = right
                if counts[(left, right)] == 1:  # Check if this interval only appears once (not overlapped)
                    visible_count += 1
        return visible_count
 

The code in other languages (Java, C++, Go) follows the same algorithmic approach, with the differences mainly in syntax and data structure implementations. The core logic of interval creation, sorting, and traversal remains consistent across all languages.