Problem Description

You are given a street represented as a number line with buildings on it. Each building is described by a 2D array buildings, where buildings[i] = [start_i, end_i, height_i] means there's a building with height height_i occupying the half-closed interval [start_i, end_i).

Your task is to describe the heights of all buildings on the street using the minimum number of non-overlapping segments. Each segment should represent a continuous portion of the street where buildings exist, along with their average height.

The output should be a 2D array street where each element street[j] = [left_j, right_j, average_j] represents:

• A half-closed interval [left_j, right_j) on the street
• The average height average_j of all buildings in that interval

Key Points:

• If multiple buildings overlap at any position, their heights contribute to the average at that position
• The average is calculated using integer division (sum of heights divided by number of buildings)
• Consecutive segments with the same average height should be merged into one segment
• Areas with no buildings should be excluded from the output
• A half-closed interval [a, b) includes point a but excludes point b

Example: For buildings = [[1,5,2],[3,10,4]]:

• From position 1 to 3: only the first building exists with height 2, so average = 2/1 = 2
• From position 3 to 5: both buildings exist with heights 2 and 4, so average = (2+4)/2 = 3
• From position 5 to 10: only the second building exists with height 4, so average = 4/1 = 4
• Result: [[1,3,2],[3,5,3],[5,10,4]]

Intuition

The key insight is that we need to track when buildings start and end, and how these events affect the total height and count of buildings at any given position on the street.

Think of walking along the street from left to right. As we move, buildings either start (adding to both the total height and count) or end (subtracting from both). These are the only positions where the average height can change.

This naturally leads us to think about event-based processing. We only need to care about positions where something changes - either a building starts or ends. Between these events, the average height remains constant.

To efficiently track these changes, we can use the difference array concept:

• When a building starts at position start, we increment the building count by 1 and add its height to the total
• When a building ends at position end, we decrement the building count by 1 and subtract its height from the total

By processing these events in sorted order (from left to right along the street), we can maintain a running sum of:

• The current total height s of all active buildings
• The current number m of active buildings

At each event position, if there are active buildings (m > 0), we calculate the average as s // m. This gives us a segment from the last event position to the current position with this average height.

The final optimization is merging consecutive segments with the same average height. If the segment we're about to add has the same average as the previous segment AND they're adjacent (no gap between them), we can extend the previous segment instead of creating a new one.

This approach ensures we visit each critical position exactly once and produce the minimum number of segments by merging wherever possible.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a difference array technique combined with hash tables to efficiently process building events.

Step 1: Initialize Data Structures

We use two hash tables:

• cnt: A defaultdict(int) to track the change in the number of buildings at each position
• d: A defaultdict(int) to track the change in total height at each position

Step 2: Process Building Events

For each building [start, end, height]:

• At position start:
  • cnt[start] += 1 (one more building starts)
  • d[start] += height (add its height to the total)
• At position end:
  • cnt[end] -= 1 (one building ends)
  • d[end] -= height (subtract its height from the total)

Step 3: Process Events in Sorted Order

We initialize:

• s = 0: running sum of current total height
• m = 0: running count of current active buildings
• last = -1: position of the last processed event
• ans = []: result array

We sort the positions in d and process them from left to right:

for k, v in sorted(d.items()):

For each position k:

1. Calculate segment for previous interval: If m > 0 (there were active buildings), we have a valid segment from last to k:

   • Calculate average: avg = s // m
   • Check if we can merge with the previous segment:
     • If ans is not empty AND
     • The last segment's average equals current avg AND
     • The last segment ends exactly at last (adjacent segments)
     • Then extend the last segment: ans[-1][1] = k
   • Otherwise, add a new segment: ans.append([last, k, avg])

2. Update running values:

   • s += v: Update total height with the change at position k
   • m += cnt[k]: Update building count with the change at position k
   • last = k: Update the last processed position

Step 4: Return Result

The ans array contains the minimum number of segments describing the street, with consecutive segments of the same average height already merged.

Time Complexity: O(n log n) where n is the number of buildings, due to sorting the event positions.

Space Complexity: O(n) for storing the hash tables and result array.

Example Walkthrough

Let's trace through a small example: buildings = [[1,5,2],[3,10,4]]

Step 1: Build Event Maps

We create two hash tables to track changes:

• When building [1,5,2] starts at position 1: add 1 to count, add 2 to height
• When building [1,5,2] ends at position 5: subtract 1 from count, subtract 2 from height
• When building [3,10,4] starts at position 3: add 1 to count, add 4 to height
• When building [3,10,4] ends at position 10: subtract 1 from count, subtract 4 from height

Resulting maps:

• cnt = {1: 1, 5: -1, 3: 1, 10: -1}
• d = {1: 2, 5: -2, 3: 4, 10: -4}

Step 2: Process Events in Sorted Order

Initialize: s = 0 (total height), m = 0 (building count), last = -1, ans = []

Process position 1:

• Since m = 0 (no previous buildings), skip segment creation
• Update: s = 0 + 2 = 2, m = 0 + 1 = 1, last = 1

Process position 3:

• Since m = 1 > 0, create segment [1, 3] with average 2 // 1 = 2
• Add [1, 3, 2] to ans
• Update: s = 2 + 4 = 6, m = 1 + 1 = 2, last = 3

Process position 5:

• Since m = 2 > 0, create segment [3, 5] with average 6 // 2 = 3
• Check merge: last segment is [1, 3, 2] with average 2 ≠ 3, so no merge
• Add [3, 5, 3] to ans
• Update: s = 6 - 2 = 4, m = 2 - 1 = 1, last = 5

Process position 10:

• Since m = 1 > 0, create segment [5, 10] with average 4 // 1 = 4
• Check merge: last segment is [3, 5, 3] with average 3 ≠ 4, so no merge
• Add [5, 10, 4] to ans
• Update: s = 4 - 4 = 0, m = 1 - 1 = 0, last = 10

Final Result: [[1,3,2],[3,5,3],[5,10,4]]

This correctly represents:

• From 1 to 3: only building 1 (height 2)
• From 3 to 5: both buildings (heights 2 and 4, average 3)
• From 5 to 10: only building 2 (height 4)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation sorted(d.items()). The dictionary d contains at most 2n entries (where n is the number of buildings), since each building contributes at most 2 unique positions (start and end). Sorting these entries takes O(2n × log(2n)) which simplifies to O(n × log n). The initial loop to populate the dictionaries takes O(n) time, and the final loop to build the answer takes O(n) time. Therefore, the overall time complexity is O(n × log n).

Space Complexity: O(n)

The space complexity comes from the auxiliary data structures used:

• Dictionary cnt: stores at most 2n entries → O(n)
• Dictionary d: stores at most 2n entries → O(n)
• List ans: in the worst case, stores O(n) intervals → O(n)
• The sorted operation creates a temporary list of size O(n)

The total space complexity is therefore O(n), where n is the number of buildings.

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

Common Pitfalls

1. Incorrectly Handling Overlapping Buildings

Pitfall: A common mistake is trying to process buildings individually or attempting to merge overlapping intervals first, which can lead to incorrect average calculations. For instance, if you process buildings sequentially and try to maintain segments directly, you might incorrectly calculate averages when buildings partially overlap.

Example of incorrect approach:

# WRONG: Processing buildings one by one
for start, end, height in buildings:
    # Trying to directly insert segments
    result.append([start, end, height])
    # Then trying to merge overlapping segments

Solution: Use the event-based approach with difference arrays. By tracking changes at specific positions rather than intervals, you ensure that all overlapping buildings are correctly accounted for at each position.

2. Forgetting to Merge Adjacent Segments with Same Average

Pitfall: The problem requires the minimum number of segments. A common error is forgetting to merge consecutive segments that have the same average height, resulting in unnecessary fragmentation.

Example of the issue:

# If buildings = [[1,3,2],[3,5,2]]
# Without merging: [[1,3,2],[3,5,2]]  # WRONG - 2 segments
# With merging: [[1,5,2]]              # CORRECT - 1 segment

Solution: Always check if the current segment can be merged with the previous one:

if (result and 
    result[-1][2] == average_height and 
    result[-1][1] == last_position):  # Adjacent check
    result[-1][1] = current_position  # Extend previous segment

3. Using Floating-Point Division Instead of Integer Division

Pitfall: The problem specifically states that averages should be calculated using integer division. Using floating-point division (/) instead of integer division (//) will produce incorrect results.

Wrong:

average_height = total_height / building_count  # Returns float

Correct:

average_height = total_height // building_count  # Returns integer

4. Not Properly Tracking Building Count Changes

Pitfall: Only tracking height changes without properly tracking the number of buildings at each position. This leads to division errors or incorrect averages.

Example of incomplete tracking:

# WRONG: Only tracking heights
for start, end, height in buildings:
    height_changes[start] += height
    height_changes[end] -= height
    # Missing: building_count_changes tracking!

Solution: Maintain separate tracking for both building counts and heights:

building_count_changes[start] += 1
building_count_changes[end] -= 1
height_changes[start] += height
height_changes[end] -= height

5. Processing Events in Wrong Order

Pitfall: Not sorting the positions before processing them. The algorithm requires processing events from left to right to correctly maintain running totals.

Wrong:

# Processing in arbitrary order
for k, v in height_changes.items():  # Not sorted!

Correct:

for k, v in sorted(height_changes.items()):  # Sorted by position

6. Including Empty Intervals in the Result

Pitfall: Adding segments where no buildings exist (where building_count = 0). The problem states that areas with no buildings should be excluded.

Solution: Only create segments when there are active buildings:

if building_count > 0:  # Only process if buildings exist
    average_height = total_height // building_count
    # Add segment to result