2345. Finding the Number of Visible Mountains

Problem Description

The problem provides us with an array of peaks, where each peak is represented by its coordinates (x_i, y_i). These coordinates define the peak of a mountain which is shaped as a right-angled isosceles triangle, with its base along the x-axis. The sides of the mountain follow lines with gradients +1 and -1 respectively. This means that the mountains expand equally both up and down from the peak. A mountain is said to be visible if its peak is not obscured by any other mountain.

To determine if a mountain is visible, we must check that no other peak exists at a higher y-value for any given x-value that lies within the base range of the mountain we are examining. The objective is to count how many mountains remain visible when considering this criterion.

Intuition

To solve this problem, we start by transforming the peak coordinates into the form (left, right), representing the leftmost and rightmost points of the mountain's base. This is done by subtracting and adding the y value to the x value of the peak respectively since we know the slopes are 1 and -1. By converting the coordinates this way, we create an interval for each mountain, and our task becomes akin to finding how many non-overlapping intervals there are.

Next, we sort the transformed array arr based on the leftmost point, and in case of a tie, the one with a farther rightmost point comes first. We initialize cur to negative infinity to represent the most right position we've covered so far.

As we iterate over sorted intervals, we can ignore any interval that ends before or exactly at cur since it means this mountain is completely hidden by another. If we find an interval where the rightmost point extends beyond cur, that means we've encountered a visible mountain.

However, there is a subtle detail. If we have duplicate intervals (Counter(arr) keeps track), it means two mountains have the same base and exactly overlap. In this case, we cannot count both as visible since one obscures the other, so we ensure we count a mountain as visible only if its interval (left, right) is unique, which is validated by the condition cnt[(l, r)] == 1.

With this approach, we can accurately count the number of visible mountains and return that as our answer.

Learn more about Stack, Sorting and Monotonic Stack patterns.

Solution Approach

The solution approach involves several key steps, each utilizing fundamental algorithms and data structures:

1. Transformation of coordinates: We first convert the peaks array into an arr of (left, right) tuples, where left and right establish the boundaries of the base of the mountains. Essentially, this is just an application of the formula (x - y, x + y) for each peak (x, y). This part of the code uses list comprehension for transformation:

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

2. Counting duplicates: Before sorting, we count how many times each (left, right) tuple appears using Counter from the collections module. This is essential to identifying mountains that share a base and thus cannot both be visible:

   1cnt = Counter(arr)

3. Sorting: We then sort the arr by the left value of each tuple and in case of ties, by the right value, in descending order. The reason for sorting by right in descending order is to ensure that, in case of overlapping bases, the mountain with the wider base will be considered first. This makes use of a custom sorting function using the key parameter of the sort method:

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

4. Iterating and counting visible mountains: To count the mountains, we iterate through the sorted arr. We keep track of the cur maximum right value seen so far, starting from negative infinity. If the right value of the current interval is less than or equal to cur, we skip this mountain as it is not visible. If not, we update cur to the right value of this mountain and increment the ans counter if the (left, right) tuple is unique (cnt[(l, r)] == 1). The use of a for loop along with conditional statements can be seen here:

   1ans, cur = 0, -inf
   2for l, r in arr:
   3    if r <= cur:
   4        continue
   5    cur = r
   6    if cnt[(l, r)] == 1:
   7        ans += 1

5. Returning the result: After iterating through all the mountains, the ans variable holds the count of visible mountains, so we simply return that value:

   1return ans

This approach cleverly transforms the problem into an interval overlapping problem with unique intervals, which is then solved with sorting and line sweeping.

Example Walkthrough

Let's consider a small example with an array of peak coordinates: [ (2, 3), (6, 1), (5, 2) ].

1. Transformation of coordinates: For each peak (x, y) we'll convert it to (left, right) by applying the formula (x - y, x + y).

   • For the peak (2, 3), the transformed coordinates are (-1, 5).
   • For the peak (6, 1), the transformed coordinates are (5, 7).
   • For the peak (5, 2), the transformed coordinates are (3, 7).

   So now our arr looks like this: [ (-1, 5), (5, 7), (3, 7) ]

2. Counting duplicates: We count how many times each (left, right) tuple appears since overlapping bases can obscure each other. Using the Counter function we get:

   1cnt = { (-1, 5): 1, (5, 7): 1, (3, 7): 1 }

   No duplicates are found in this case.

3. Sorting: We sort arr by the left value and then by the right value in descending order. After sorting, our arr looks like this:

   1sorted arr = [ (-1, 5), (3, 7), (5, 7) ]

   The array is already sorted by the left values, and there are no ties to consider for the right values in descending order.

4. Iterating and counting visible mountains: We now count the visible mountains:

   • We start with ans = 0 and cur = -inf.
   • The first interval (-1, 5) has right value 5, which is greater than cur, so it is visible. We set cur = 5 and since it's unique, increment ans to 1.
   • The second interval (3, 7) has right value 7, which is greater than cur, so it is visible. We set cur = 7 and since it's unique, increment ans to 2.
   • The third interval (5, 7) starts at 5, but its right value is not greater than cur, which means it's not visible because it's fully within the range of the second mountain. We do not increment ans.

5. Returning the result: We went through all the mountains and concluded that 2 are visible. So, the final answer returned is 2.

Solution Implementation

Time and Space Complexity

The provided Python code defines a function visibleMountains that computes the number of visible mountains given an array of peaks. Each peak is represented as a list with two integers. The time complexity and space complexity for each part of the algorithm are:

• Transforming peaks to arr, where a tuple (x - y, x + y) is created for each peak (x, y): takes O(n), where n is the length of the peaks array. The space complexity is also O(n) due to the storage of the transformed arr list.

• Counting elements with Counter(arr): this operation has a time complexity of O(n) because it iterates once over the arr. The space complexity is O(n) for storing the count of each unique tuple in arr.

• Sorting arr using arr.sort(key=lambda x: (x[0], -x[1])): the time complexity for sorting in this case is O(n log n) because it uses the TimSort algorithm (Python's built-in sorting algorithm), which has this time complexity on average. Since sorting is done in place, the space complexity remains O(1).

• Iterating over the sorted arr and computing the visible mountains: the time complexity is O(n), as it requires a single pass through the array. The variable cur is used to keep track of the highest right point seen so far, and ans is used to count the number of unique, visible mountains. This part does not require additional space, so the space complexity is O(1).

Overall, the time complexity of the entire function is dominated by the sorting part, which is O(n log n). The space complexity is determined by the additional data structures, primarily the transformation list and the counter, both of which are O(n). Thus, the total space complexity is O(n).

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