Average Height of Buildings in Each Segment

Average Height of Buildings in Each Segment - Problem

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 buildings). You may return the array in any order.

Note: 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.

Input & Output

Example 1 — Basic Overlapping Buildings

$ Input: buildings = [[1,3,3],[2,4,4],[5,7,1]]

› Output: [[1,2,3],[2,3,3],[3,4,4],[5,7,1]]

💡 Note: From 1 to 2: only building 1 with height 3. From 2 to 3: buildings 1 and 2, average = (3+4)/2 = 3. From 3 to 4: only building 2 with height 4. From 5 to 7: only building 3 with height 1.

Example 2 — Complete Overlap

$ Input: buildings = [[1,5,2],[3,10,4]]

› Output: [[1,3,2],[3,5,3],[5,10,4]]

💡 Note: From 1 to 3: only first building (height 2). From 3 to 5: both buildings overlap, average = (2+4)/2 = 3. From 5 to 10: only second building (height 4).

Example 3 — Single Building

$ Input: buildings = [[0,2,3]]

› Output: [[0,2,3]]

💡 Note: Only one building from 0 to 2 with height 3, so result is straightforward single segment.

Constraints

1 ≤ buildings.length ≤ 1000
0 ≤ starti < endi ≤ 10⁸
1 ≤ heighti ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Buildings

Buildings with [start, end, height] on a number line

Find Overlaps

Identify where buildings overlap and create segments

Calculate Averages

Compute average height for each segment

Key Takeaway

🎯 Key Insight: Critical points where buildings start/end naturally divide the street into segments with consistent average heights

Asked in

G Google 15 a Amazon 12 M Microsoft 8 Apple 5

The key insight is to identify critical points where building coverage changes, then process segments between these points. The event-based sweep line approach efficiently tracks overlapping buildings by processing start/end events. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Position	O(n × range)	O(range)	Check every coordinate position to find which buildings overlap
Event-Based Sweep Line	O(n log n)	O(n)	Process building start/end events to efficiently track height changes

Brute Force - Check Every Position — Algorithm Steps

Step 1: Find the range of all coordinates from start to end
Step 2: For each coordinate, check which buildings cover it
Step 3: Calculate average height for each position
Step 4: Group consecutive positions with same average into segments

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Positions

Check each coordinate from start to end

Find Buildings

For each position, see which buildings cover it

Calculate Average

Average the heights of overlapping buildings

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int** solution(int** buildings, int buildingsSize, int* buildingsColSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    if (buildingsSize == 0) return NULL;
    
    // Find coordinate range
    int minPos = INT_MAX, maxPos = INT_MIN;
    for (int i = 0; i < buildingsSize; i++) {
        if (buildings[i][0] < minPos) minPos = buildings[i][0];
        if (buildings[i][1] > maxPos) maxPos = buildings[i][1];
    }
    
    int** result = malloc(1000 * sizeof(int*));
    *returnColumnSizes = malloc(1000 * sizeof(int));
    int prevAvg = -1;
    int segmentStart = minPos;
    
    for (int pos = minPos; pos < maxPos; pos++) {
        int heightSum = 0;
        int count = 0;
        
        // Check which buildings cover this position
        for (int i = 0; i < buildingsSize; i++) {
            if (buildings[i][0] <= pos && pos < buildings[i][1]) {
                heightSum += buildings[i][2];
                count++;
            }
        }
        
        if (count == 0) {
            if (prevAvg != -1) {
                result[*returnSize] = malloc(3 * sizeof(int));
                result[*returnSize][0] = segmentStart;
                result[*returnSize][1] = pos;
                result[*returnSize][2] = prevAvg;
                (*returnColumnSizes)[*returnSize] = 3;
                (*returnSize)++;
                prevAvg = -1;
            }
            continue;
        }
        
        int currentAvg = heightSum / count;
        
        if (currentAvg != prevAvg) {
            if (prevAvg != -1) {
                result[*returnSize] = malloc(3 * sizeof(int));
                result[*returnSize][0] = segmentStart;
                result[*returnSize][1] = pos;
                result[*returnSize][2] = prevAvg;
                (*returnColumnSizes)[*returnSize] = 3;
                (*returnSize)++;
            }
            segmentStart = pos;
            prevAvg = currentAvg;
        }
    }
    
    // Add final segment
    if (prevAvg != -1) {
        result[*returnSize] = malloc(3 * sizeof(int));
        result[*returnSize][0] = segmentStart;
        result[*returnSize][1] = maxPos;
        result[*returnSize][2] = prevAvg;
        (*returnColumnSizes)[*returnSize] = 3;
        (*returnSize)++;
    }
    
    return result;
}

int main() {
    // Simple parsing for demonstration
    int buildings[][3] = {{1,3,3},{2,4,4},{5,7,1}};
    int* buildingPtrs[] = {buildings[0], buildings[1], buildings[2]};
    int colSizes[] = {3, 3, 3};
    int returnSize;
    int* returnColumnSizes;
    
    int** result = solution(buildingPtrs, 3, colSizes, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d,%d,%d]", result[i][0], result[i][1], result[i][2]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × range)

For each position in the coordinate range, we check all n buildings

✓ Linear Growth

Space Complexity

O(range)

We store height information for each coordinate position

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Position — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler