How hard is LeetCode 1199. Minimum Time to Build Blocks?

LeetCode 1199. Minimum Time to Build Blocks is rated Hard on LeetCode.

What is the time complexity of LeetCode 1199. Minimum Time to Build Blocks?

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

What is the space complexity of LeetCode 1199. Minimum Time to Build Blocks?

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

What topics does LeetCode 1199. Minimum Time to Build Blocks cover?

LeetCode 1199. Minimum Time to Build Blocks is tagged Greedy, Array, Math and Heap (Priority Queue) on LeetCode.

Is LeetCode 1199. Minimum Time to Build Blocks a premium problem?

Yes. LeetCode 1199. Minimum Time to Build Blocks is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Minimum Time to Build Blocks — LeetCode 1199 Python Solution

HardLeetCode PremiumGreedyArrayMathHeap (Priority Queue)

Problem: #1199
Pattern: Heap / Priority Queue
Reading time: 2 min
Source: leetcode.com

The problem

You are given a list of blocks, where blocks[i] = t means that the i-th block needs t units of time to be built. A block can only be built by exactly one worker.

Example

Input: blocks = [1], split = 1
Output: 1
Explanation: We use 1 worker to build 1 block in 1 time unit.

Python solution

Python

class Solution:
    def minBuildTime(self, blocks: List[int], split: int) -> int:
        heapify(blocks)
        while len(blocks) > 1:
            heappop(blocks)
            heappush(blocks, heappop(blocks) + split)
        return blocks[0]

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 1199. Minimum Time to Build Blocks 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 1199. Minimum Time to Build Blocks?: LeetCode 1199. Minimum Time to Build Blocks is rated Hard on LeetCode.
What is the time complexity of LeetCode 1199. Minimum Time to Build Blocks?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 1199. Minimum Time to Build Blocks?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1199. Minimum Time to Build Blocks cover?: LeetCode 1199. Minimum Time to Build Blocks is tagged Greedy, Array, Math and Heap (Priority Queue) on LeetCode.
Is LeetCode 1199. Minimum Time to Build Blocks a premium problem?: Yes. LeetCode 1199. Minimum Time to Build Blocks is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.