LeetCode 2015 - Average Height of Buildings in Each Segment
The problem describes a street as a number line, and each building occupies a half-closed interval [start, end) with a fixed height.
Difficulty: 🟡 Medium
Topics: Array, Sorting, Heap (Priority Queue), Prefix Sum
Solution
Problem Understanding
The problem describes a street as a number line, and each building occupies a half-closed interval [start, end) with a fixed height. Multiple buildings may overlap, and for every point on the street covered by at least one building, we want to compute the average height of all active buildings.
The result must be represented as the minimum number of non-overlapping segments. Each segment should contain a continuous range where the average height remains constant.
The important detail is that buildings use half-open intervals. A building starting at x is active at x, while a building ending at x is no longer active there. This affects how events are processed when multiple buildings start or end at the same coordinate.
For example:
[1,4,2]
[3,9,4]
Between 1 and 3, only height 2 exists.
Between 3 and 4, both buildings overlap, so the average becomes:
(2 + 4) / 2 = 3
Between 4 and 9, only height 4 remains.
The constraints are large:
- Up to
10^5buildings - Coordinates up to
10^8
This immediately tells us that we cannot simulate every coordinate on the number line. The coordinates are far too large and sparse. Instead, we need an event-based or sweep line approach that only processes positions where something changes.
The output may be returned in any order, but most implementations naturally generate segments in sorted order.
Several edge cases are important:
- Multiple buildings may start or end at the same coordinate.
- Different overlapping configurations may still produce the same average, allowing adjacent segments to merge.
- Empty gaps between buildings must not appear in the output.
- Integer division must be used for averages.
- Consecutive segments with the same average should be merged into one larger segment.
Approaches
Brute Force Approach
A naive solution would attempt to evaluate every coordinate on the street and determine which buildings cover that point.
For each position:
- Find all buildings active there.
- Compute the average height.
- Extend the segment while the average remains unchanged.
This approach is correct because it explicitly computes the answer for every location. However, it is completely impractical because coordinates can reach 10^8.
Even if we compressed coordinates and checked every interval independently, a naive scan over all buildings for every interval would still be too slow.
Suppose there are n buildings and m unique coordinates. A brute force coordinate-compression solution could require:
O(n * m)
In the worst case, m is 2n, leading to O(n^2) complexity.
With 10^5 buildings, this is infeasible.
Key Insight
The average only changes at building boundaries.
Between two consecutive event coordinates, the set of active buildings never changes. Therefore:
- The total height sum remains constant.
- The active building count remains constant.
- The average remains constant.
This means we only need to process positions where buildings start or end.
We can use a sweep line algorithm:
-
Add a building's height when we reach its start.
-
Remove a building's height when we reach its end.
-
Maintain:
-
total active height sum
-
number of active buildings
For every interval between consecutive event positions, we compute:
average = total_height // active_count
Then we merge adjacent intervals with identical averages.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Recomputes active buildings repeatedly |
| Optimal | O(n log n) | O(n) | Sweep line with event sorting |
Algorithm Walkthrough
- Create an event list for all building boundaries.
For each building [start, end, height]:
- Add an event at
startindicating the building becomes active. - Add an event at
endindicating the building becomes inactive.
We store:
(position, height_change, count_change)
Specifically:
start -> (+height, +1)
end -> (-height, -1)
- Sort all events by position.
This allows us to process the street from left to right in order. 3. Maintain running state variables.
We track:
current_height_sumcurrent_count
These represent the active buildings immediately after processing events at a coordinate. 4. Process intervals between consecutive event positions.
Suppose the previous coordinate is prev_x and the current coordinate is x.
The active building configuration remains constant throughout:
[prev_x, x)
Therefore:
average = current_height_sum // current_count
if current_count > 0.
5. Skip empty regions.
If current_count == 0, there are no buildings active in that interval, so we do not add anything to the result.
6. Merge adjacent segments with identical averages.
If the last recorded segment:
[a, prev_x, avg]
has the same average as the current interval and is directly adjacent, we extend it:
[a, x, avg]
instead of creating a new segment.
7. After recording the interval, process all events at coordinate x.
Update:
current_height_sum += height_change
current_count += count_change
- Continue until all event positions are processed.
Why it works
The key invariant is that between any two consecutive event coordinates, the set of active buildings never changes. Since the active set is constant, both the total height and the building count remain constant, meaning the average height is also constant throughout that interval.
Because the algorithm processes all building boundaries in sorted order and updates the active set exactly when buildings start or end, every interval receives the correct average. Merging adjacent equal-average segments guarantees the minimum number of output segments.
Python Solution
from typing import List
from collections import defaultdict
class Solution:
def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:
events = defaultdict(lambda: [0, 0])
for start, end, height in buildings:
events[start][0] += height
events[start][1] += 1
events[end][0] -= height
events[end][1] -= 1
positions = sorted(events.keys())
result = []
current_height_sum = 0
current_count = 0
for i in range(len(positions) - 1):
x = positions[i]
height_delta, count_delta = events[x]
current_height_sum += height_delta
current_count += count_delta
next_x = positions[i + 1]
if current_count == 0:
continue
average = current_height_sum // current_count
if (
result
and result[-1][1] == x
and result[-1][2] == average
):
result[-1][1] = next_x
else:
result.append([x, next_x, average])
return result
The implementation begins by building an event map. Each coordinate stores two cumulative values:
- change in total height
- change in active building count
Using a dictionary allows multiple buildings starting or ending at the same coordinate to be merged efficiently.
After sorting all coordinates, the algorithm sweeps from left to right. At each coordinate:
- Apply all building start/end updates.
- Compute the interval extending to the next coordinate.
- Skip the interval if no buildings are active.
- Compute the integer average.
- Merge with the previous segment if possible.
The merging logic is important because consecutive intervals may produce identical averages even when the active building set changes.
For example:
[1,3) average = 2
[3,5) average = 2
These must become:
[1,5) average = 2
The solution runs efficiently within the problem constraints.
Go Solution
package main
import "sort"
func averageHeightOfBuildings(buildings [][]int) [][]int {
type Event struct {
heightDelta int
countDelta int
}
events := map[int]Event{}
for _, b := range buildings {
start, end, height := b[0], b[1], b[2]
e1 := events[start]
e1.heightDelta += height
e1.countDelta += 1
events[start] = e1
e2 := events[end]
e2.heightDelta -= height
e2.countDelta -= 1
events[end] = e2
}
positions := make([]int, 0, len(events))
for pos := range events {
positions = append(positions, pos)
}
sort.Ints(positions)
result := [][]int{}
currentHeightSum := 0
currentCount := 0
for i := 0; i < len(positions)-1; i++ {
x := positions[i]
event := events[x]
currentHeightSum += event.heightDelta
currentCount += event.countDelta
nextX := positions[i+1]
if currentCount == 0 {
continue
}
average := currentHeightSum / currentCount
if len(result) > 0 &&
result[len(result)-1][1] == x &&
result[len(result)-1][2] == average {
result[len(result)-1][1] = nextX
} else {
result = append(result, []int{x, nextX, average})
}
}
return result
}
The Go implementation follows the same sweep line logic as the Python solution.
A struct is used to store event deltas cleanly. Since Go maps return copies of structs, we retrieve the struct, modify it, then write it back into the map.
Slices are used for the final result. Integer division in Go naturally matches the problem requirement.
Because coordinate values can reach 10^8 and heights up to 10^5, standard Go int is safe on LeetCode's 64-bit environment.
Worked Examples
Example 1
Input:
[[1,4,2],[3,9,4]]
Step 1: Build Events
| Position | Height Delta | Count Delta |
|---|---|---|
| 1 | +2 | +1 |
| 3 | +4 | +1 |
| 4 | -2 | -1 |
| 9 | -4 | -1 |
Sorted positions:
[1, 3, 4, 9]
Step 2: Sweep
| Interval | Active Height Sum | Active Count | Average | Output |
|---|---|---|---|---|
| [1,3) | 2 | 1 | 2 | [1,3,2] |
| [3,4) | 6 | 2 | 3 | [3,4,3] |
| [4,9) | 4 | 1 | 4 | [4,9,4] |
Final result:
[[1,3,2],[3,4,3],[4,9,4]]
Example 2
Input:
[[1,3,2],[2,5,3],[2,8,3]]
Step 1: Events
| Position | Height Delta | Count Delta |
|---|---|---|
| 1 | +2 | +1 |
| 2 | +6 | +2 |
| 3 | -2 | -1 |
| 5 | -3 | -1 |
| 8 | -3 | -1 |
Sorted positions:
[1,2,3,5,8]
Step 2: Sweep
| Interval | Height Sum | Count | Average | Action |
|---|---|---|---|---|
| [1,2) | 2 | 1 | 2 | add |
| [2,3) | 8 | 3 | 2 | merge |
| [3,5) | 6 | 2 | 3 | add |
| [5,8) | 3 | 1 | 3 | merge |
Merged result:
[[1,3,2],[3,8,3]]
Example 3
Input:
[[1,2,1],[5,6,1]]
Step 1: Events
| Position | Height Delta | Count Delta |
|---|---|---|
| 1 | +1 | +1 |
| 2 | -1 | -1 |
| 5 | +1 | +1 |
| 6 | -1 | -1 |
Step 2: Sweep
| Interval | Height Sum | Count | Average | Output |
|---|---|---|---|---|
| [1,2) | 1 | 1 | 1 | add |
| [2,5) | 0 | 0 | skip | |
| [5,6) | 1 | 1 | add |
Final result:
[[1,2,1],[5,6,1]]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Sorting event coordinates dominates |
| Space | O(n) | Event storage and output |
Each building contributes exactly two events, so there are at most 2n unique coordinates. Sorting these coordinates requires O(n log n) time. The sweep itself is linear.
The memory usage is linear because we store event data and the resulting segments.
Test Cases
sol = Solution()
# Example 1
assert sol.averageHeightOfBuildings(
[[1,4,2],[3,9,4]]
) == [[1,3,2],[3,4,3],[4,9,4]]
# Example 2, verifies merging equal averages
assert sol.averageHeightOfBuildings(
[[1,3,2],[2,5,3],[2,8,3]]
) == [[1,3,2],[3,8,3]]
# Example 3, verifies gaps are skipped
assert sol.averageHeightOfBuildings(
[[1,2,1],[5,6,1]]
) == [[1,2,1],[5,6,1]]
# Single building
assert sol.averageHeightOfBuildings(
[[2,7,5]]
) == [[2,7,5]]
# Complete overlap
assert sol.averageHeightOfBuildings(
[[1,5,2],[1,5,4]]
) == [[1,5,3]]
# Nested buildings
assert sol.averageHeightOfBuildings(
[[1,10,10],[3,7,2]]
) == [[1,3,10],[3,7,6],[7,10,10]]
# Same average after changing active set
assert sol.averageHeightOfBuildings(
[[1,4,2],[2,5,2]]
) == [[1,5,2]]
# Multiple events at same coordinate
assert sol.averageHeightOfBuildings(
[[1,3,2],[3,5,4]]
) == [[1,3,2],[3,5,4]]
# Large coordinate values
assert sol.averageHeightOfBuildings(
[[0,100000000,1]]
) == [[0,100000000,1]]
# Many identical buildings
assert sol.averageHeightOfBuildings(
[[1,5,3],[1,5,3],[1,5,3]]
) == [[1,5,3]]
Test Summary
| Test | Why |
|---|---|
| Example 1 | Basic overlapping intervals |
| Example 2 | Verifies segment merging |
| Example 3 | Verifies empty gaps are excluded |
| Single building | Simplest valid input |
| Complete overlap | Multiple active buildings entire time |
| Nested buildings | Tests entering and leaving overlap |
| Same average after changing set | Ensures merging logic is correct |
| Multiple events at same coordinate | Tests half-open interval handling |
| Large coordinate values | Confirms no coordinate simulation |
| Many identical buildings | Tests repeated contributions |
Edge Cases
One important edge case occurs when multiple buildings start and end at the same coordinate. Incorrect event ordering can easily produce invalid intervals or wrong averages. The implementation avoids this issue by aggregating all updates at the same coordinate before processing the interval to the next coordinate. This ensures the active set is always correct for the half-open interval semantics.
Another subtle case occurs when different active building configurations produce the same average. For example:
[1,3): average = 2
[3,5): average = 2
Even though the active buildings changed at position 3, the final output should merge these intervals into a single segment. The implementation explicitly checks whether the previous segment ends exactly where the current one begins and whether the averages match.
A third important edge case is empty space between buildings. The street representation must exclude regions with no buildings. During the sweep, if the active building count becomes zero, the implementation skips that interval entirely. This prevents invalid segments like:
[start, end, 0]
from appearing in the result.
A final edge case involves very large coordinates. Since coordinates can reach 10^8, any coordinate-by-coordinate simulation would fail. The sweep line approach only processes event boundaries, making the algorithm scalable regardless of coordinate magnitude.