Average Height Of Buildings In Each Segment - Leetcode Solution

Problem statement:

You are given an array buildings representing the heights of buildings on a street numbered from 0 to n - 1 where buildings[i] represents the height of the ith building.

The city has been divided into segments, and each segment contains buildings. You are given an array segments where segments[j] = [leftj, rightj, incj].

leftj and rightj represent the indices of the leftmost and rightmost buildings in the jth segment respectively (0-indexed).

incj represents the increase in the height of all buildings within the jth segment.

Return an integer array res of size n where res[i] represents the new height of the ith building after all the segments have been applied.

Constraints:

1 <= buildings.length <= 10^5 0 <= buildings[i], incj <= 10^5 1 <= segments.length <= 10^4 segments[j].length == 3 0 <= leftj <= rightj < n Explanation:

We can solve the problem by using an approach called difference array. With difference array, we can calculate the height of each building after applying all segments.

Difference array is an auxiliary array that stores the difference between consecutive values of the original array. In this case, we use a difference array to store the differences between the height of buildings to the left and right of each segment.

We can then apply the increments of each segment to the difference array. Finally, we can calculate the height of each building using the difference array.

Algorithm:

1. Create a difference array diff of size n. Set all values in diff to 0.
2. For each segment, update diff[leftj] by incj and diff[rightj + 1] by -incj.
3. Calculate the cumulative sum of diff.
4. For each building i, calculate the new height as buildings[i] + diff[i]. Store the result in res[i].
5. Return res.

Time Complexity: O(n+k), where k is the number of segments. Space Complexity: O(n)

Python Code:

def averageHeight(buildings: List[int], segments: List[List[int]]) -> List[int]: n = len(buildings) diff = [0] * n

# update difference array
for left, right, inc in segments:
    diff[left] += inc
    if right + 1 < n:
        diff[right + 1] -= inc

# calculate cumulative sum
for i in range(1, n):
    diff[i] += diff[i-1]

# calculate new heights
res = []
for i in range(n):
    res.append(buildings[i] + diff[i])

return res

1