Brick Wall

How it works

Instead of checking every possible vertical position, we can think about this differently. We want to maximize the number of gaps we pass through, because each gap means we avoid cutting a brick. If we count how many times each gap position appears across all rows, the position with the most gaps is the best place to draw our line. The answer is then total rows minus the maximum gap count.

Steps

1. Use a hash map to count the frequency of each gap position across all rows.
2. For each row, compute cumulative brick widths (excluding the last brick to avoid counting the wall edge).
3. For each cumulative width, increment its count in the hash map.
4. Find the maximum count in the hash map (the position with the most aligned gaps).
5. Return the total number of rows minus this maximum count.

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.

Things to watch for

Counting the Wall Edge as a Valid Gap

The rightmost edge of the wall (at position equal to total width) should not be counted as a gap since a line there wouldn't cross any bricks anyway. Including it inflates the gap count and gives wrong answers.

Returning Maximum Gaps Instead of Minimum Cuts

The answer is number_of_rows - max_gaps, not just max_gaps. Maximizing gaps minimizes cuts, but forgetting to subtract from total rows returns the wrong value.

Not Handling Rows with Single Bricks

If a row contains only one brick spanning the entire width, it has no internal gaps. The hash map initialization with {0: 0} handles the edge case where no gaps exist, ensuring the answer defaults to cutting through all rows.

from typing import List

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())

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> countGap;
        countGap[0] = 0;

        for (const auto& row : wall) {
            int total = 0;
            for (size_t i = 0; i < row.size() - 1; ++i) {
                total += row[i];
                countGap[total]++;
            }
        }

        int maxGaps = 0;
        for (const auto& [key, value] : countGap) {
            maxGaps = max(maxGaps, value);
        }

        return wall.size() - maxGaps;
    }
};