Solution Explanation: Average Height of Buildings in Each Segment

This problem requires finding the minimum number of non-overlapping segments that represent the average height of buildings along a street. The input is a list of buildings, each defined by a start position, end position, and height. The output is a list of segments, each defined by a start position, end position, and the average height of buildings within that segment.

The optimal approach leverages the concept of a difference array and efficient data structures like hash maps (or dictionaries in Python) and sorted maps (or sorted dictionaries) to achieve an efficient solution.

Algorithm:

1. Data Structures:

   • cnt: A hash map (or dictionary) to store the change in the number of buildings at each position. cnt[x] represents the increase or decrease in the number of buildings overlapping position x. An increase is represented by a positive value, and a decrease by a negative value.
   • d: A sorted map (or sorted dictionary) to store the change in the total height of buildings at each position. d[x] represents the increase or decrease in the total height at position x.

2. Preprocessing:

   • Iterate through the buildings array. For each building [start, end, height]:
     • Add 1 to cnt[start] and -1 to cnt[end]. This accounts for the building starting and ending at those positions.
     • Add height to d[start] and subtract height from d[end]. This tracks the change in total height at each position.

3. Processing the Difference Arrays:

   • Initialize s (sum of heights) and m (number of buildings) to 0.
   • Initialize last to -1 to track the start of the current segment.
   • Iterate through the sorted keys of d (this is crucial for processing positions in order):
     • If m > 0 (buildings exist in the current segment):
       • Calculate the average height (avg = s // m).
       • If there's a previous segment in ans and its average height and end position match the current average and the last processed position, merge the current segment with the previous one (updating the end position of the previous segment).
       • Otherwise, add a new segment [last, k, avg] to the ans array.
     • Update s by adding v (the change in height at the current position).
     • Update m by adding cnt[k] (the change in the number of buildings at the current position).
     • Update last to k.

4. Return:

   • Return the ans array containing the segments with their average heights.

Time Complexity: O(N log N), where N is the number of buildings. The sorting of d dominates the complexity.

Space Complexity: O(N), to store the cnt and d maps and the ans array (in the worst case, where all buildings are distinct).

Example Code (Python):

from collections import defaultdict
 
class Solution:
    def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:
        cnt = defaultdict(int)
        d = defaultdict(int)
        for start, end, height in buildings:
            cnt[start] += 1
            cnt[end] -= 1
            d[start] += height
            d[end] -= height
        s = m = 0
        last = -1
        ans = []
        for k, v in sorted(d.items()):
            if m:
                avg = s // m
                if ans and ans[-1][2] == avg and ans[-1][1] == last:
                    ans[-1][1] = k
                else:
                    ans.append([last, k, avg])
            s += v
            m += cnt[k]
            last = k
        return ans

The code in other languages (Java, C++, Go, TypeScript) follows a very similar structure, adapting the data structures and syntax to their respective languages. The core algorithmic idea remains consistent.