Average Height of Buildings in Each Segment

#360 Most AskedMedium

Average Height of Buildings in Each Segment #360 Most Asked

Medium

Microsoft

2 views

Topics:

ArraysGreedy Algorithms

You are given a 2D integer array buildings where buildings[i] = [start_i, end_i, height_i].

You are standing on the x-axis and want to build some skyscrapers. The i^th skyscraper should be built in the segment [start_i, end_i] and have an equal height of height_i.

Return a list of disjoint segments of the x-axis representing the skyline of the skyscrapers. Each segment should be represented as a sorted list [start, end, height] of distinct heights over each contiguous horizontal segment.

Note that:

All the given segments are closed intervals.
The skyline should be in the same ordering as the given input buildings.
The skyline should cover the exact same area as the buildings.
There should not be any adjacent horizontal lines of equal height in the output skyline.

Example 1:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,3,10],[3,7,15],[7,9,10],[9,12,12],[15,19,10],[19,20,8],[20,24,0]]
Explanation:
The figure shows the skyline of the buildings.
The red lines represent the boundaries of the skyline.

Example 2:

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,5,3]]
Explanation:
The figure shows the skyline of the buildings.
The red lines represent the boundaries of the skyline.

Constraints:

1 <= buildings.length <= 10⁴
0 <= start_i < end_i <= 10⁵
1 <= height_i <= 10⁵
buildings is sorted by start_i in strictly increasing order.

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 expected range for the start, end, and height values? Are they integers or floating-point numbers?
Could the input `buildings` list be empty or null? What should I return in that case?
If building segments overlap, how should the average height be calculated at the overlapping regions? Is it a simple average of the heights of all overlapping buildings at that point?
Is the input `buildings` list guaranteed to be sorted by the start position, or do I need to handle unsorted input?
Can the start and end positions of a building segment be the same (i.e., zero-length segments)? If so, how should those segments be handled?

Brute Force Solution

Approach

The brute force approach calculates the average building height for every possible segment combination. We consider every possible start and end point for each segment to find all segment averages. It's like trying out every single combination until we've explored all possibilities.

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

Imagine you want to find the average height in a section of buildings.
Start with the first building and consider it alone as a segment. Calculate its average height (which is just its own height).
Now, expand the segment to include the first two buildings. Calculate the average height of these two buildings.
Continue expanding the segment to include the first three buildings, then the first four, and so on, each time calculating the average height until you reach the last building.
Next, start with the second building and repeat the process. Consider the second building alone, then the second and third buildings, then the second, third, and fourth buildings, and so on.
Keep doing this, shifting the starting point one building at a time, and calculating the average for all possible segment lengths until you've started at every single building.
You will now have a list of every possible segment and its average height. Then, compare the average heights.

Code Implementation

def average_height_of_buildings_in_each_segment(building_heights, max_number_of_segments):
    best_arrangement = None
    best_average_heights = []

    number_of_buildings = len(building_heights)

    for number_of_segments in range(1, min(number_of_buildings + 1, max_number_of_segments + 1)):
        # Iterate through all possible number of segments up to the max
        for segment_indices in find_all_possible_segment_indices(number_of_buildings, number_of_segments):
            average_heights_for_segments = []

            for i in range(number_of_segments):
                start_index = segment_indices[i - 1] if i > 0 else 0
                end_index = segment_indices[i] if i < number_of_segments - 1 else number_of_buildings

                # Calculate the sum of building heights in the current segment
                segment_height_sum = sum(building_heights[start_index:end_index])
                segment_length = end_index - start_index

                # Calculate the average building height for the current segment.
                average_height = segment_height_sum / segment_length if segment_length > 0 else 0
                average_heights_for_segments.append(average_height)

            # In this case, we pick the arrangement that maximizes the minimum average height
            if not best_average_heights or min(average_heights_for_segments) > min(best_average_heights):
                best_arrangement = segment_indices
                best_average_heights = average_heights_for_segments

    return best_average_heights

def find_all_possible_segment_indices(number_of_buildings, number_of_segments):
    if number_of_segments == 1:
        return [[]]

    if number_of_segments > number_of_buildings:
        return []

    segment_indices_list = []

    # Recursively find segment indices
    for i in range(1, number_of_buildings - number_of_segments + 2):
        remaining_segment_indices = find_all_possible_segment_indices(number_of_buildings - i, number_of_segments - 1)

        for remaining_indices in remaining_segment_indices:
            segment_indices = [i + index for index in remaining_indices]
            segment_indices_list.append([i] + segment_indices)

    return segment_indices_list

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible segments of the input array of size n. The outer loop determines the starting point of the segment, and the inner loop expands the segment to include subsequent buildings. For each starting point, the number of expansions decreases as the starting point shifts, resulting in a nested loop structure where, in the worst case, each building potentially forms a segment with every building that follows. This leads to a total number of operations proportional to the sum of integers from 1 to n, which can be approximated as n * (n+1) / 2, thereby simplifying to O(n²).

Space Complexity

O(1) – The described brute force approach primarily uses a few variables to track the start and end indices of segments and to calculate the average height for each segment. It doesn't explicitly mention storing all the calculated averages or creating any auxiliary data structures whose size scales with the input size N (number of buildings). Therefore, the space used remains constant irrespective of the input size, resulting in O(1) space complexity.

Optimal Solution

Approach

We need to calculate the average building height for different segments of a city. The clever trick is to precompute the sum of heights for every possible starting point so we can quickly calculate averages later.

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

First, calculate and store the cumulative sum of the building heights up to each building. This means for each building, you know the total height of all buildings up to that point.
When you need to calculate the average height for a specific segment of buildings, use the stored cumulative sums to quickly determine the total height of buildings in that segment. You can do this by subtracting the cumulative sum before the segment from the cumulative sum at the end of the segment.
Divide the total height of the segment by the number of buildings in the segment to get the average height.
Repeat this process for each segment you need to analyze. Because you pre-calculated the cumulative sums, calculating the average for each segment is now very fast.

Code Implementation

def average_heights_of_buildings_in_each_segment(building_heights, segments):
    average_heights = []
    current_total_height = 0
    current_building_count = 0

    for segment_index in range(len(segments)):
        start_index, end_index = segments[segment_index]

        # Initialize if it's the first segment.
        if segment_index == 0:
            for building_index in range(start_index, end_index + 1):
                current_total_height += building_heights[building_index]
                current_building_count += 1
        else:
            previous_start_index, previous_end_index = segments[segment_index - 1]

            # Add new buildings to the segment.
            for building_index in range(previous_end_index + 1, end_index + 1):
                current_total_height += building_heights[building_index]
                current_building_count += 1

            # Remove buildings leaving the segment.
            for building_index in range(start_index, previous_start_index):
                current_total_height -= building_heights[building_index]
                current_building_count -= 1

        # Need to avoid division by zero
        if current_building_count > 0:
            average_height = current_total_height / current_building_count
        else:
            average_height = 0

        average_heights.append(average_height)

    return average_heights

Big(O) Analysis

Time Complexity

O(n) – The solution first calculates the cumulative sum of building heights in a single pass through the input array of size n. This operation takes O(n) time. Subsequently, calculating the average height for a given segment involves a few constant-time operations (subtraction and division) using the precomputed cumulative sums. If we were to perform this calculation for k segments, the additional time would be O(k). However, the question asks the complexity of the provided solution, including the initial precomputation. Assuming we only need to calculate the cumulative sum array once, the overall time complexity is dominated by the initial cumulative sum calculation. Therefore, the total time complexity is O(n).

Space Complexity

O(N) – The algorithm calculates and stores the cumulative sum of building heights in an auxiliary array. This array has the same size as the input array of building heights, which we denote as N. Therefore, the extra space required to store the cumulative sums grows linearly with the number of buildings, N. No other significant data structures are used, making the auxiliary space complexity O(N).

Edge Cases

Case	How to Handle
Empty input list of buildings	Return an empty list since there are no buildings to process.
Buildings with zero height	Treat buildings with zero height as normal buildings, contributing to the average height calculation if overlapping with other buildings.
Overlapping buildings with identical start and end positions but different heights	The solution must correctly accumulate the heights when calculating the average at the shared start and end positions.
Buildings with start and end positions that are very close together (floating-point precision)	Consider using a small tolerance value when comparing start and end positions to avoid issues with floating-point precision.
Buildings with very large height values (potential integer overflow)	Use appropriate data types (e.g., long) to prevent integer overflow during height summation.
Buildings that are completely contained within other buildings	Ensure that the average height is calculated correctly at the start and end points of the inner buildings.
Buildings with very large start and end positions (potential memory issues)	Consider using a more memory-efficient data structure or algorithm if the range of start and end positions is extremely large and sparse.
No overlap between any buildings	The solution should correctly return individual segments with their corresponding heights, creating non-overlapping segments.

Empty input list of buildings

How to Handle:

Return an empty list since there are no buildings to process.

Buildings with zero height

How to Handle:

Treat buildings with zero height as normal buildings, contributing to the average height calculation if overlapping with other buildings.

Overlapping buildings with identical start and end positions but different heights

How to Handle:

The solution must correctly accumulate the heights when calculating the average at the shared start and end positions.

Buildings with start and end positions that are very close together (floating-point precision)

How to Handle:

Consider using a small tolerance value when comparing start and end positions to avoid issues with floating-point precision.

Buildings with very large height values (potential integer overflow)

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow during height summation.

Buildings that are completely contained within other buildings

How to Handle:

Ensure that the average height is calculated correctly at the start and end points of the inner buildings.

Buildings with very large start and end positions (potential memory issues)

How to Handle:

Consider using a more memory-efficient data structure or algorithm if the range of start and end positions is extremely large and sparse.

No overlap between any buildings

How to Handle:

The solution should correctly return individual segments with their corresponding heights, creating non-overlapping segments.