MediumNo. 0554

Brick Wall — LeetCode 554 Python Solution

Pattern
Hash Map
Topics
Array, Hash Table
Reading time
2 min

The problem

There is a rectangular brick wall in front of you with n rows of bricks. The ith row has some number of bricks each of the same height (i.e., one unit) but they can be of different widths.

Example

Input
wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output
2

Python solution

PythonSolution
class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        cnt = Counter()
        for row in wall:
            s = 0
            for x in row[:-1]:
                s += x
                cnt[s] += 1
        return len(wall) - max(cnt.values(), default=0)

Complexity

Time
O(m × n)
Space · auxiliary
O(n)

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 554. Brick Wall is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0560Subarray Sum Equals KMedium
0001Two SumEasy
0036Valid SudokuMedium
0037Sudoku SolverHard
0041First Missing PositiveHard
0049Group AnagramsMedium

Frequently asked questions

How hard is LeetCode 554. Brick Wall?

LeetCode 554. Brick Wall is rated Medium on LeetCode.

What is the time complexity of LeetCode 554. Brick Wall?

The Python solution on this page runs in O(m × n).

What is the space complexity of LeetCode 554. Brick Wall?

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

What topics does LeetCode 554. Brick Wall cover?

LeetCode 554. Brick Wall is tagged Array and Hash Table on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.