554. Brick Wall - Explanation

1. Brute Force

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        n = len(wall)
        m = 0
        for brick in wall[0]:
            m += brick

        gaps = [[] for _ in range(n)]
        for i in range(n):
            gap = 0
            for brick in wall[i]:
                gap += brick
                gaps[i].append(gap)

        res = n
        for line in range(1, m):
            cuts = 0
            for i in range(n):
                if line not in gaps[i]:
                    cuts += 1

            res = min(res, cuts)
        return res

Time & Space Complexity

Time complexity: $O(m * n * g)$
Space complexity: $O(n * g)$

Where $m$ is the sum of widths of the bricks in the first row, $n$ is the number of rows and $g$ is the average number of gaps in each row.

2. Hash Map

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        countGap = {0: 0}

        for r in wall:
            total = 0
            for i in range(len(r) - 1):
                total += r[i]
                countGap[total] = 1 + countGap.get(total, 0)

        return len(wall) - max(countGap.values())

Time & Space Complexity

Time complexity: $O(N)$
Space complexity: $O(g)$

Where $N$ is the total number of bricks in the wall and $g$ is the total number of gaps in all the rows.