What is the time complexity of LeetCode 2015. Average Height of Buildings in Each Segment?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 2015. Average Height of Buildings in Each Segment?

The Python solution on this page uses O(n) auxiliary space.

Is LeetCode 2015. Average Height of Buildings in Each Segment a premium problem?

Yes. LeetCode 2015. Average Height of Buildings in Each Segment is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Average Height of Buildings in Each Segment — LeetCode 2015 Python Solution

MediumLeetCode PremiumGreedyArraySortingHeap (Priority Queue)

Problem: #2015
Pattern: Heap / Priority Queue
Reading time: 4 min
Source: leetcode.com

The 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].

Example

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.

Python solution

Python

class Solution:
    def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:
        cnt = defaultdict(int)
        d = defaultdict(int)
        for start, end, height in buildings:
            cnt[start] += 1
            cnt[end] -= 1
            d[start] += height
            d[end] -= height
        s = m = 0
        last = -1
        ans = []
        for k, v in sorted(d.items()):
            if m:
                avg = s // m
                if ans and ans[-1][2] == avg and ans[-1][1] == last:
                    ans[-1][1] = k
                else:
                    ans.append([last, k, avg])
            s += v
            m += cnt[k]
            last = k
        return ans

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2015. Average Height of Buildings in Each Segment is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2015. Average Height of Buildings in Each Segment?: LeetCode 2015. Average Height of Buildings in Each Segment is rated Medium on LeetCode.
What is the time complexity of LeetCode 2015. Average Height of Buildings in Each Segment?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 2015. Average Height of Buildings in Each Segment?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2015. Average Height of Buildings in Each Segment cover?: LeetCode 2015. Average Height of Buildings in Each Segment is tagged Greedy, Array, Sorting and Heap (Priority Queue) on LeetCode.
Is LeetCode 2015. Average Height of Buildings in Each Segment a premium problem?: Yes. LeetCode 2015. Average Height of Buildings in Each Segment is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.