Skip to main content
Talentd

Average Height of Buildings in Each Segment - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedySortingHeap (Priority Queue)12 min readAsked at: Microsoft
Practice this problem

Problem Statement

A perfectly straight street is represented by a number line. The street has building(s) on it and is represented by a 2D integer array buildings, where buildings[i] = [starti, endi, heighti]. This means that there is a building with heighti in the half-closed segment [starti, endi).

You want to describe the heights of the buildings on the street with the minimum number of non-overlapping segments. The street can be represented by the 2D integer array street where street[j] = [leftj, rightj, averagej] describes a half-closed segment [leftj, rightj) of the road where the average heights of the buildings in the segment is averagej.

  • For example, if buildings = [[1,5,2],[3,10,4]], the street could be represented by street = [[1,3,2],[3,5,3],[5,10,4]] because:
    • From 1 to 3, there is only the first building with an average height of 2 / 1 = 2.
    • From 3 to 5, both the first and the second building are there with an average height of (2+4) / 2 = 3.
    • From 5 to 10, there is only the second building with an average height of 4 / 1 = 4.

Given buildings, return the 2D integer array street as described above (excluding any areas of the street where there are no buldings). You may return the array in any order.

The average of n elements is the sum of the n elements divided (integer division) by n.

A half-closed segment [a, b) is the section of the number line between points a and b including point a and not including point b.

 

Example 1:

Input: buildings = [[1,4,2],[3,9,4]]
Output: [[1,3,2],[3,4,3],[4,9,4]]
Explanation:
From 1 to 3, there is only the first building with an average height of 2 / 1 = 2.
From 3 to 4, both the first and the second building are there with an average height of (2+4) / 2 = 3.
From 4 to 9, there is only the second building with an average height of 4 / 1 = 4.

Example 2:

Input: buildings = [[1,3,2],[2,5,3],[2,8,3]]
Output: [[1,3,2],[3,8,3]]
Explanation:
From 1 to 2, there is only the first building with an average height of 2 / 1 = 2.
From 2 to 3, all three buildings are there with an average height of (2+3+3) / 3 = 2.
From 3 to 5, both the second and the third building are there with an average height of (3+3) / 2 = 3.
From 5 to 8, there is only the last building with an average height of 3 / 1 = 3.
The average height from 1 to 3 is the same so we can group them into one segment.
The average height from 3 to 8 is the same so we can group them into one segment.

Example 3:

Input: buildings = [[1,2,1],[5,6,1]]
Output: [[1,2,1],[5,6,1]]
Explanation:
From 1 to 2, there is only the first building with an average height of 1 / 1 = 1.
From 2 to 5, there are no buildings, so it is not included in the output.
From 5 to 6, there is only the second building with an average height of 1 / 1 = 1.
We cannot group the segments together because an empty space with no buildings seperates the segments.

 

Constraints:

  • 1 <= buildings.length <= 105
  • buildings[i].length == 3
  • 0 <= starti < endi <= 108
  • 1 <= heighti <= 105

Approach Overview

Problem Overview: You receive a list of buildings represented as [start, end, height]. Buildings overlap on a number line, and the goal is to split the street into minimal segments where the average height of active buildings stays constant. Each output segment should report [left, right, averageHeight] after considering all buildings covering that range.

Approach 1: Brute Force Coordinate Expansion (O(n * R) time, O(R) space)

A straightforward idea is to expand the entire coordinate range and compute the average height at every unit position. For each building, iterate from start to end and track the cumulative height and building count. After processing all buildings, compute the average height for every coordinate and merge adjacent positions with the same value into segments. This approach is simple but impractical when coordinates are large because the runtime depends on the numeric range R, not just the number of buildings.

Approach 2: Sweep Line with Sorted Events (O(n log n) time, O(n) space)

Instead of expanding every coordinate, treat each building boundary as an event. Create two events: one when a building starts and another when it ends. Sort all events by position using techniques similar to problems on sorting and sweep line processing. As you move left to right, maintain the current total height and active building count. Between two consecutive event positions, the average height remains constant, so you can emit a segment using avg = totalHeight / count. This significantly reduces work because only boundary points are processed.

Approach 3: Difference Array + Hash Table (O(n log n) time, O(n) space)

The optimal implementation uses a difference map to track how the active height sum and building count change at boundaries. For each building, update two entries in a hash table: at start add +height and +1 to the active count; at end subtract them. After collecting all updates, sort the keys and iterate through them in order. Maintain running totals of height sum and building count while scanning segments between consecutive coordinates. The average for a segment becomes heightSum / count. Merge adjacent segments if their averages match. This approach avoids expanding coordinates and processes only boundary changes, making it efficient and scalable. It commonly appears in interval problems involving arrays, sweep-line strategies, and event aggregation similar to skyline-style questions.

Recommended for interviews: The difference array + hash table sweep approach is the expected solution. Interviewers want to see that you convert interval updates into boundary events and maintain running aggregates. Mentioning the brute-force range expansion demonstrates baseline reasoning, but implementing the difference-map sweep shows strong understanding of interval processing and scalable algorithm design.

Solution

We can use the difference array concept, utilizing a hash table cnt to record the change in the number of buildings at each position, and another hash table d to record the change in height at each position.

Next, we sort the hash table d by its keys, use a variable s to record the current total height, and a variable m to record the current number of buildings.

Then, we traverse the hash table d. For each position, if m is not 0, it means there are buildings at the previous positions. We calculate the average height. If the average height of the buildings at the current position is the same as that of the previous buildings, we merge them; otherwise, we add the current position to the result set.

Finally, we return the result set.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of buildings.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Coordinate ExpansionO(n * R)O(R)Small coordinate ranges where expanding every position is feasible
Sweep Line with Sorted EventsO(n log n)O(n)General interval problems where boundaries define state changes
Difference Array + Hash TableO(n log n)O(n)Optimal approach for large coordinate ranges and overlapping buildings

Video Solution

2015. Average Height of Buildings in Each Segment (Leetcode Medium) • Programming Live with Larry • 283 views views

Frequently Asked Questions

Is Average Height of Buildings in Each Segment easy or hard?
The problem is rated Medium because the logic is straightforward once you recognize the sweep-line pattern. The main challenge is converting overlapping intervals into boundary events and correctly computing averages while merging adjacent segments.
Average Height of Buildings in Each Segment Python/Java solution
Most implementations build a map from coordinate to two values: change in height sum and change in building count. After sorting the coordinates, iterate through them while maintaining running totals and emit segments with average height. The same logic translates cleanly across Python, Java, C++, Go, and TypeScript.
How to solve Average Height of Buildings in Each Segment in O(n)?
Pure O(n) is difficult because building boundaries must usually be processed in sorted order. The typical approach collects start and end updates in a difference map, sorts those coordinates, then performs a sweep to compute averages. The practical optimal complexity is O(n log n).
What is the best approach for Average Height of Buildings in Each Segment?
The most efficient method uses a difference array with a hash table and a sweep over sorted coordinates. Each building contributes +height/+1 at its start and -height/-1 at its end. After sorting boundary points, maintain a running height sum and building count to compute the average for each segment. This runs in O(n log n) time and O(n) space.
Is Average Height of Buildings in Each Segment asked at Google/Amazon/Meta?
Interval sweep and skyline-style problems appear frequently in interviews at companies like Google, Amazon, and Meta. This problem tests the same skills: handling overlapping intervals, converting updates into boundary events, and maintaining running aggregates during a sweep line.
What data structure is used in Average Height of Buildings in Each Segment?
The core structure is a hash table (or map) storing difference updates at building boundaries. During processing, the keys are sorted and scanned sequentially while maintaining running totals. Arrays and sorting are also involved when building the event list.
What is the time complexity of Average Height of Buildings in Each Segment?
The optimal solution runs in O(n log n) time due to sorting the boundary coordinates created from building start and end points. The sweep itself is linear over the sorted keys. Space complexity is O(n) for storing the difference map and event boundaries.

Ready to solve this problem?

Practice Average Height of Buildings in Each Segment with our built-in code editor and test cases.

Practice on FleetCode
Previous

Amount of New Area Painted Each Day

Next

Average Waiting Time