Count Covered Buildings

Medium

Asked by:

4 views

Topics:

Arrays

You are given a positive integer n, representing an n x n city. You are also given a 2D grid buildings, where buildings[i] = [x, y] denotes a unique building located at coordinates [x, y].

A building is covered if there is at least one building in all four directions: left, right, above, and below.

Return the number of covered buildings.

Example 1:

Input: n = 3, buildings = [[1,2],[2,2],[3,2],[2,1],[2,3]]

Output: 1

Explanation:

Only building [2,2] is covered as it has at least one building:
- above ([1,2])
- below ([3,2])
- left ([2,1])
- right ([2,3])
Thus, the count of covered buildings is 1.

Example 2:

Input: n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]

Output: 0

Explanation:

No building has at least one building in all four directions.

Example 3:

Input: n = 5, buildings = [[1,3],[3,2],[3,3],[3,5],[5,3]]

Output: 1

Explanation:

Only building [3,3] is covered as it has at least one building:
- above ([1,3])
- below ([5,3])
- left ([3,2])
- right ([3,5])
Thus, the count of covered buildings is 1.

Constraints:

2 <= n <= 10⁵
1 <= buildings.length <= 10⁵
buildings[i] = [x, y]
1 <= x, y <= n
All coordinates of buildings 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 is the data type of the building heights? Can they be floating-point numbers or negative?
What are the maximum and minimum possible values for the building heights, and what is the maximum number of buildings I should expect in the input?
If no buildings are covered, should I return 0 or a specific error code like -1?
Are the building positions always contiguous and sorted by position? Or do I need to account for gaps or unsorted order?
Could you define 'covered'? Does a building need to be strictly shorter than at least one building to its left and one to its right, or is 'less than or equal to' sufficient?

Brute Force Solution

Approach

We're given buildings and need to figure out how many are completely covered by others. The brute force method will check every building against every other building to see if one fully covers the other.

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

Take the first building in the list.
Compare that building to every other building to see if the first building is completely covered by any of them.
If we find a building that covers it, mark the first building as covered and move on.
If we go through all the other buildings and none cover the first one, mark it as not covered.
Now, repeat this process for the second building in the list.
Keep going until you have done this check for every building in the list.
Finally, count up all the buildings you marked as covered to find the total number of covered buildings.

Code Implementation

def count_covered_buildings_brute_force(buildings):
    number_of_buildings = len(buildings)
    covered_buildings_count = 0
    covered_status = [False] * number_of_buildings

    for current_building_index in range(number_of_buildings):
        # Iterate through all other buildings
        for other_building_index in range(number_of_buildings):
            # Avoid comparing a building to itself
            if current_building_index == other_building_index:
                continue

            current_building_start = buildings[current_building_index][0]
            current_building_end = buildings[current_building_index][1]
            other_building_start = buildings[other_building_index][0]
            other_building_end = buildings[other_building_index][1]

            # Check if the current building is covered
            if (other_building_start <= current_building_start and\
                other_building_end >= current_building_end):

                # Mark current building as covered
                covered_status[current_building_index] = True

                # No need to check other buildings
                break

    # Count the number of covered buildings
    for status in covered_status:
        if status:
            covered_buildings_count += 1

    return covered_buildings_count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n buildings. For each building, it compares it against every other building in the list to check for coverage. This comparison involves another loop that iterates up to n times in the worst case. Therefore, the dominant operation involves a nested loop structure, where the outer loop runs n times, and the inner loop also runs up to n times for each iteration of the outer loop, resulting in approximately n * n comparisons. This leads to O(n²).

Space Complexity

O(N) – The algorithm iterates through each building and needs to keep track of whether each building is covered or not. This requires an auxiliary data structure, such as a boolean array, of size N, where N is the number of buildings, to store the 'covered' status for each building. No other significant data structures are used besides this 'covered' array. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The core idea is to think of each building as casting a shadow, and we want to find the total length of the ground covered by these shadows. Instead of checking each tiny piece of ground, we'll focus on the start and end points of these shadows, sorting them to process them in the correct order.

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

Create a list of important points. For each building, add two points: its starting location and its ending location (the start plus the width). Store the building's height along with these points.
Sort these points based on their location. This ensures we process the 'shadows' from left to right.
Go through the points one by one. Keep track of all the building heights that are currently 'active' (meaning, their shadows are currently covering the ground at that location).
Whenever we reach a new point, update the list of active building heights. If it's a start point, add the height to the list. If it's an end point, remove the height from the list.
After updating the active heights, find the maximum height among the active buildings. This represents the height of the 'covered area' at that location.
Calculate the covered distance. Multiply the maximum active height by the distance to the next point. Add this value to your running total of covered area.
Repeat until you have processed all the points. The final total covered area is the result.

Code Implementation

def count_covered_buildings(buildings):
    important_points = []
    for start, end, height in buildings:
        important_points.append((start, height, 1)) # 1 marks start
        important_points.append((end, height, -1))  # -1 marks end

    important_points.sort(key=lambda x: x[0])

    active_heights = []
    total_covered_area = 0
    previous_location = 0

    for location, height, point_type in important_points:
        # Calculate covered area since last point
        if active_heights:
            max_active_height = max(active_heights)
            total_covered_area += max_active_height * (location - previous_location)

        # Update active heights based on point type
        if point_type == 1:
            # Starting point: add height to active heights.
            active_heights.append(height)

        else:
            # Ending point: remove height from active heights.
            active_heights.remove(height)

            # Removing the current height from active_heights

        previous_location = location

    return total_covered_area

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm's runtime is dominated by sorting the points in step 2, which takes O(n log n) time where n is the number of buildings (each building generates two points). The subsequent loop iterates through these sorted points, updating the active building heights. Inserting and deleting into the active building heights (implemented as a sorted data structure like a heap or balanced tree) takes O(log n) per point. Finding the maximum active height also takes O(log n) using a heap or balanced tree. Since we iterate through n points, these operations amount to O(n log n). Therefore, the overall time complexity is O(n log n) + O(n log n) which simplifies to O(n log n).

Space Complexity

O(N) – The algorithm creates a list of important points, which stores two points (start and end) for each building. Thus, the size of this list is proportional to the number of buildings, N. The algorithm also keeps track of active building heights, which in the worst-case scenario, could store all N building heights simultaneously. Therefore, the auxiliary space used is proportional to N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
buildings is null or empty	Return 0 because there are no buildings to cover
buildings contains only one building	Return 0 because at least two buildings are required to form a covered range
buildings array contains very large numbers	Ensure the data type used to store heights or positions can accommodate these large numbers, preventing potential overflow
buildings array contains duplicate positions	Handle duplicates by considering only the building with the maximum height at that position to maximize coverage
buildings are already completely covered by existing ranges	The algorithm should correctly return 0 if all buildings are already within the covered ranges
buildings array contains overlapping ranges	The algorithm should merge overlapping ranges into a single, larger range to accurately count the covered buildings
buildings array size approaches the maximum allowed limit	Optimize for space complexity to prevent memory exhaustion when processing a very large number of buildings
Integer overflow when calculating the covered length	Use a data type with a larger range, such as long, to store the length of the covered range.

buildings is null or empty

How to Handle:

Return 0 because there are no buildings to cover

buildings contains only one building

How to Handle:

Return 0 because at least two buildings are required to form a covered range

buildings array contains very large numbers

How to Handle:

Ensure the data type used to store heights or positions can accommodate these large numbers, preventing potential overflow

buildings array contains duplicate positions

How to Handle:

Handle duplicates by considering only the building with the maximum height at that position to maximize coverage

buildings are already completely covered by existing ranges

How to Handle:

The algorithm should correctly return 0 if all buildings are already within the covered ranges

buildings array contains overlapping ranges

How to Handle:

The algorithm should merge overlapping ranges into a single, larger range to accurately count the covered buildings

buildings array size approaches the maximum allowed limit

How to Handle:

Optimize for space complexity to prevent memory exhaustion when processing a very large number of buildings

Integer overflow when calculating the covered length

How to Handle:

Use a data type with a larger range, such as long, to store the length of the covered range.