Finding the Number of Visible Mountains

Medium

Asked by:

14 views

Topics:

ArraysGreedy Algorithms

You are given a 0-indexed 2D integer array peaks where peaks[i] = [x_i, y_i] represents the coordinates of the i^th mountain peak in a mountain range.

A mountain is visible if its peak is not hidden behind any other peak. In other words, the i^th mountain is not visible if there exists an integer j such that 0 <= j < peaks.length and i != j, where both x_j >= x_i and y_j >= y_i are satisfied.

Return the number of visible mountains.

Example 1:

Input: peaks = [[0,1],[1,3],[3,7],[5,5],[4,2]]
Output: 3
Explanation:
- Mountain at index 0 is visible because no other mountain has a peak to its right and higher.
- Mountain at index 1 is not visible because the mountain at index 2 has a peak to its right and higher.
- Mountain at index 2 is visible because no other mountain has a peak to its right and higher.
- Mountain at index 3 is visible because no other mountain has a peak to its right and higher.
- Mountain at index 4 is not visible because the mountain at index 3 has a peak to its right and higher.
There are 3 visible mountains so we return 3.

Example 2:

Input: peaks = [[1,0],[2,2],[0,1]]
Output: 2
Explanation:
- Mountain at index 0 is visible because no other mountain has a peak to its right and higher.
- Mountain at index 1 is visible because no other mountain has a peak to its right and higher.
- Mountain at index 2 is not visible because the mountain at index 1 has a peak to its right and higher.
There are 2 visible mountains so we return 2.

Constraints:

1 <= peaks.length <= 10⁵
0 <= x_i, y_i <= 10⁵
All the given peaks are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the range of x and h values? Can they be negative, zero, or floating-point numbers?
What should I return if no mountains are visible?
If two mountains have the same visible region, should they be counted as distinct visible mountains?
How large can the input list of mountains be?
Can mountains have the same (x, h) values? If so, how does that affect visibility?

Brute Force Solution

Approach

The brute force approach to counting visible mountains means we're going to check every single mountain against every other mountain. We are going to directly simulate what it means for one mountain to block another from view. This will be very thorough, but probably slow for a large number of mountains.

Here's how the algorithm would work step-by-step:

For each mountain in our group, we're going to assume it is initially visible.
Then, we'll compare that mountain with every other mountain.
When comparing two mountains, we need to check if the second mountain is taller and in front of the first mountain.
If the second mountain is taller and blocks the view of the first mountain, we'll mark the first mountain as not visible.
We'll repeat this process of comparing each mountain to all others to see if it's blocked.
Finally, after comparing each mountain to every other mountain, we count how many mountains are still marked as visible. This is our final answer.

Code Implementation

def find_number_of_visible_mountains_brute_force(mountain_positions, mountain_heights):
    number_of_mountains = len(mountain_positions)
    is_mountain_visible = [True] * number_of_mountains

    # Assume all mountains are visible initially

    for current_mountain_index in range(number_of_mountains):
        for other_mountain_index in range(number_of_mountains):
            # Skip comparison with itself
            if current_mountain_index == other_mountain_index:
                continue

            # Check if the other mountain is in front
            if mountain_positions[other_mountain_index] > mountain_positions[current_mountain_index]:

                # Check if the other mountain is taller               if mountain_heights[other_mountain_index] >= mountain_heights[current_mountain_index]:

                    # If taller, it blocks current mountain                   is_mountain_visible[current_mountain_index] = False
                    break

    visible_mountain_count = 0
    for visible in is_mountain_visible:
        if visible:
            visible_mountain_count += 1

    return visible_mountain_count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n mountains. For each mountain, it compares it with every other mountain which takes O(n) time. The nested iteration of checking each mountain against all others drives the overall cost. Therefore, we have n iterations, each taking n operations, resulting in roughly n * n comparisons. This simplifies to a Big O time complexity of O(n²).

Space Complexity

O(N) – The described brute force approach requires us to maintain a boolean array (or similar data structure) to mark whether each mountain is visible. This array has a size equal to the number of mountains, N. We initialize this array and update it throughout the process, meaning its space usage contributes to the auxiliary space. Therefore, the auxiliary space complexity is directly proportional to N.

Optimal Solution

Approach

The problem can be efficiently solved by focusing on identifying duplicate mountains and the mountains completely hidden behind others. We can determine visible mountains by strategically comparing their positions and sizes.

Here's how the algorithm would work step-by-step:

First, look at each mountain's position and height as a single combined entity.
Identify and remove any duplicate mountains, as they only contribute one visible mountain.
Sort the remaining mountains based on their position; for mountains at the same position, prioritize the taller one.
Keep track of the mountain with the furthest reaching visible boundary on both left and right sides as we traverse the sorted mountain set.
A mountain is visible only if its both its left and right edge is further than the furthest reach of all the mountains before it.
Count the mountains that meet this visibility criteria; this will be the number of visible mountains.

Code Implementation

def finding_the_number_visible_mountains(mountains):
    mountain_positions = set()
    duplicate_count = 0

    # Count duplicates, treating same positions as one mountain
    for position, height in mountains:
        if (position, height) in mountain_positions:
            duplicate_count += 1
        mountain_positions.add((position, height))

    unique_mountains = []
    mountain_positions = set()
    for position, height in mountains:
        if (position, height) not in mountain_positions:
            unique_mountains.append((position, height))
            mountain_positions.add((position, height))

    # Sort mountains by position, then by height
    sorted_mountains = sorted(unique_mountains, key=lambda x: (x[0], -x[1]))

    visible_mountains_count = 0
    leftmost_reach = float('-inf')
    rightmost_reach = float('-inf')

    for position, height in sorted_mountains:
        left_edge = position - height
        right_edge = position + height

        # A mountain is visible if it is not hidden
        if left_edge > leftmost_reach and right_edge > rightmost_reach:
            visible_mountains_count += 1

        # Update the furthest reaches
        leftmost_reach = max(leftmost_reach, right_edge)
        rightmost_reach = max(rightmost_reach, right_edge)

    return visible_mountains_count

Big(O) Analysis

Time Complexity

O(n log n) – Identifying and removing duplicate mountains involves iterating through the n mountains and comparing them, which can be done in O(n) time if using a hash set to track occurrences, or O(n log n) if sorting and comparing adjacent elements. Sorting the remaining mountains based on position (or position and height) takes O(n log n) time using an efficient sorting algorithm. Iterating through the sorted mountains to determine visibility involves a single loop that takes O(n) time. Therefore, the dominant factor is the sorting step, resulting in a total time complexity of O(n log n).

Space Complexity

O(N) – The algorithm uses auxiliary space primarily for storing the potentially de-duplicated and sorted mountains. In the worst case, where all mountains are unique, this requires a data structure (e.g., a list or array) to hold up to N mountains, where N is the number of input mountains. Additionally, sorting algorithms often utilize extra space, which in the worst case can be O(N) for algorithms like merge sort. Therefore, the overall auxiliary space is determined by the storage of these mountains, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input list of mountains.	Return 0 as there are no mountains to be visible.
All mountains have the exact same height and location.	Return 1, as only one is visible, and others are hidden.
Mountains are sorted by peak location.	Algorithm should correctly process regardless of input order; no specific handling needed.
Integer overflow when calculating the shadow range of a mountain.	Use a wider data type (e.g., long) or alternative representation for range calculations to prevent overflow.
Maximum number of mountains allowed based on memory constraints.	Ensure the algorithm's space complexity remains reasonable and within memory limits by using appropriate data structures.
Mountains are densely packed, with almost fully overlapping shadows.	Algorithm efficiently accounts for overlaps to only count truly visible mountains.
Floating point precision issues when comparing peak locations or heights.	Use a tolerance value when comparing floats to account for potential precision errors.
Negative peak locations and/or heights.	Algorithm should support negative coordinates and heights, defining visibility accordingly.

Empty input list of mountains.

How to Handle:

Return 0 as there are no mountains to be visible.

All mountains have the exact same height and location.

How to Handle:

Return 1, as only one is visible, and others are hidden.

Mountains are sorted by peak location.

How to Handle:

Algorithm should correctly process regardless of input order; no specific handling needed.

Integer overflow when calculating the shadow range of a mountain.

How to Handle:

Use a wider data type (e.g., long) or alternative representation for range calculations to prevent overflow.

Maximum number of mountains allowed based on memory constraints.

How to Handle:

Ensure the algorithm's space complexity remains reasonable and within memory limits by using appropriate data structures.

Mountains are densely packed, with almost fully overlapping shadows.

How to Handle:

Algorithm efficiently accounts for overlaps to only count truly visible mountains.

Floating point precision issues when comparing peak locations or heights.

How to Handle:

Use a tolerance value when comparing floats to account for potential precision errors.

Negative peak locations and/or heights.

How to Handle:

Algorithm should support negative coordinates and heights, defining visibility accordingly.