LeetCode 554 - Brick Wall

The problem gives us a wall made of multiple rows of bricks. Each row is represented as an array of integers, where each integer describes the width of a brick. Every brick has height 1, and all rows together form a rectangle with the same total width.

leetcodemediumarrayhash-table

LeetCode Problem 554

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

Problem Understanding

The problem gives us a wall made of multiple rows of bricks. Each row is represented as an array of integers, where each integer describes the width of a brick. Every brick has height 1, and all rows together form a rectangle with the same total width.

We want to draw a vertical line from the top of the wall to the bottom such that the line crosses the fewest bricks possible.

A very important rule is that if the vertical line passes exactly along the boundary between two bricks, then those bricks are not considered crossed. This means that the best line is usually one that aligns with as many brick edges as possible.

However, we are not allowed to draw the line along the extreme left or extreme right edge of the wall. Those positions would trivially cross zero bricks, and the problem explicitly forbids them.

The input is a two dimensional array:

wall[i] = widths of bricks in row i

For example:

wall = [[1,2,2,1],[3,1,2]]

The first row has bricks with widths:

1 | 2 | 2 | 1

The second row has:

3 | 1 | 2

The output is a single integer representing the minimum number of bricks crossed by the optimal vertical line.

The constraints tell us several important things:

  • There can be up to 10^4 rows.
  • The total number of bricks across all rows is at most 2 * 10^4.
  • Brick widths can be very large, up to 2^31 - 1.

The key observation from the constraints is that we cannot simulate every possible vertical position continuously. The width values are huge, and the wall could theoretically span billions of units. Instead, we need to focus only on meaningful positions, specifically the boundaries between bricks.

There are several important edge cases:

  • Rows consisting of a single brick. In this case there are no internal edges where the line can pass, so every row must be crossed.
  • Multiple rows sharing the same brick boundaries. This is the ideal scenario because the line can avoid crossing many bricks simultaneously.
  • Completely misaligned rows where no internal boundaries match. In that case the line crosses every row.
  • Large brick widths. We must not build arrays proportional to the wall width.

Approaches

Brute Force Approach

A straightforward approach is to consider every possible vertical position where a line could be drawn and count how many bricks it crosses.

To do this, we could:

  1. Compute all possible edge positions from every row.
  2. For each candidate position:
  • Check every row.
  • Determine whether the position lies inside a brick or exactly on a boundary.
  1. Count how many rows are crossed.
  2. Return the minimum count.

This approach is correct because it explicitly evaluates every valid line placement.

However, it is inefficient because for every candidate position we may scan all rows and possibly all bricks again. If there are B total bricks, the complexity can approach O(B^2).

Given that the total number of bricks can be up to 2 * 10^4, a quadratic approach is unnecessarily expensive.

Key Insight

Instead of directly minimizing the number of crossed bricks, we can maximize the number of rows where the line passes through a brick boundary.

Suppose the wall has n rows.

If a vertical line passes through brick boundaries in k rows, then it crosses bricks in exactly:

n - k

rows.

Therefore:

minimum crossed bricks = total rows - maximum shared edge count

This transforms the problem into a frequency counting problem.

For every row:

  • Compute the prefix sums of brick widths.
  • Each prefix sum represents an internal edge position.
  • Store how many times each edge position appears using a hash map.

We ignore the final edge because that corresponds to the right boundary of the wall, which is forbidden.

At the end:

  • Find the edge position with the highest frequency.
  • Subtract that frequency from the number of rows.

This approach is efficient because every brick is processed exactly once.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(B²) O(B) Checks many candidate positions repeatedly
Optimal O(B) O(B) Uses hash map to count shared brick edges

Here, B represents the total number of bricks across all rows.

Algorithm Walkthrough

  1. Create a hash map called edge_count.

The keys will be edge positions, and the values will store how many rows contain that edge. 2. Iterate through each row in the wall.

For every row, we compute cumulative widths using a running prefix sum. 3. Traverse all bricks in the row except the last one.

We exclude the last brick because its ending position is the wall's right edge, and drawing a line there is not allowed. 4. Update the running prefix sum.

For example, if a row is [1,2,2,1], the internal edge positions are:

1
1 + 2 = 3
3 + 2 = 5
  1. Increment the frequency for each edge position in the hash map.

This tracks how many rows share the same boundary. 6. After processing all rows, find the maximum frequency in the hash map.

This represents the vertical line that passes through the most brick boundaries. 7. Return:

number_of_rows - maximum_frequency

because those are the rows where the line must cross bricks.

Why it works

Every row either contributes a boundary at a position or forces the line to pass through a brick there. By counting how many rows share the same boundary position, we directly determine how many bricks can be avoided. Maximizing shared boundaries automatically minimizes crossed bricks.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        edge_count = defaultdict(int)

        for row in wall:
            prefix_sum = 0

            # Exclude the last brick to avoid the wall boundary
            for brick_width in row[:-1]:
                prefix_sum += brick_width
                edge_count[prefix_sum] += 1

        max_edges = max(edge_count.values(), default=0)

        return len(wall) - max_edges

The implementation follows the algorithm directly.

We use a defaultdict(int) so that unseen edge positions automatically start with count 0.

For each row, we maintain a running prefix_sum. Every prefix sum before the final brick represents a valid internal boundary position.

The expression:

row[:-1]

is very important because it excludes the final edge of the wall.

After processing all rows, we compute the largest frequency stored in the hash map. If no internal edges exist, such as when every row contains only one brick, the map will be empty. In that case we use:

default=0

to avoid an error and correctly return the total number of rows.

Finally, we subtract the maximum shared edge count from the total number of rows.

Go Solution

func leastBricks(wall [][]int) int {
    edgeCount := make(map[int]int)

    for _, row := range wall {
        prefixSum := 0

        // Exclude the last brick
        for i := 0; i < len(row)-1; i++ {
            prefixSum += row[i]
            edgeCount[prefixSum]++
        }
    }

    maxEdges := 0

    for _, count := range edgeCount {
        if count > maxEdges {
            maxEdges = count
        }
    }

    return len(wall) - maxEdges
}

The Go solution is structurally identical to the Python version.

A map[int]int is used instead of Python's dictionary. Since Go maps return the zero value for missing keys, incrementing counts is straightforward.

We explicitly loop using indices so we can stop before the final brick:

for i := 0; i < len(row)-1; i++

Go integers are sufficient here because the constraints fit within the platform's integer range.

Worked Examples

Example 1

Input:

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

We process each row and record internal edge positions.

Row Prefix Sums Added Hash Map State
[1,2,2,1] 1, 3, 5 {1:1, 3:1, 5:1}
[3,1,2] 3, 4 {1:1, 3:2, 5:1, 4:1}
[1,3,2] 1, 4 {1:2, 3:2, 5:1, 4:2}
[2,4] 2 {1:2, 2:1, 3:2, 4:2, 5:1}
[3,1,2] 3, 4 {1:2, 2:1, 3:3, 4:3, 5:1}
[1,3,1,1] 1, 4, 5 {1:3, 2:1, 3:3, 4:4, 5:2}

The maximum edge frequency is:

4

There are 6 rows total.

So:

6 - 4 = 2

Final answer:

2

Example 2

Input:

wall = [[1],[1],[1]]

Each row has only one brick.

There are no internal edges because we exclude the final wall boundary.

The hash map remains empty.

Row Prefix Sums Added Hash Map State
[1] none {}
[1] none {}
[1] none {}

Maximum edge frequency:

0

Total rows:

3

Answer:

3 - 0 = 3

Final answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(B) Every brick is processed once
Space O(B) Hash map may store every unique edge

Here, B is the total number of bricks across all rows.

The algorithm is linear because each brick contributes at most one prefix sum update. Hash map operations are average-case O(1).

The space complexity depends on how many distinct edge positions exist. In the worst case, every edge position is unique.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        edge_count = defaultdict(int)

        for row in wall:
            prefix_sum = 0

            for brick_width in row[:-1]:
                prefix_sum += brick_width
                edge_count[prefix_sum] += 1

        max_edges = max(edge_count.values(), default=0)

        return len(wall) - max_edges

solution = Solution()

# Example 1 from problem statement
assert solution.leastBricks(
    [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
) == 2

# Example 2, no internal edges exist
assert solution.leastBricks([[1],[1],[1]]) == 3

# Perfect alignment across all rows
assert solution.leastBricks([[2,2],[2,2],[2,2]]) == 0

# No shared internal boundaries
assert solution.leastBricks([[1,1],[2],[1,1]]) == 1

# Single row with multiple bricks
assert solution.leastBricks([[1,2,3]]) == 0

# Large brick widths
assert solution.leastBricks([[1000000000,1],[1,1000000000]]) == 1

# Mixed alignment positions
assert solution.leastBricks([[1,1,1],[2,1],[1,2]]) == 1

# One row only, line can pass through an internal edge
assert solution.leastBricks([[1,1]]) == 0

# Multiple repeated edge positions
assert solution.leastBricks([[3,1],[1,3],[2,2],[3,1]]) == 1

print("All test cases passed.")

Test Case Summary

Test Why
Example 1 Standard mixed alignment scenario
Example 2 No internal edges exist
Perfect alignment Best possible answer is zero
No shared boundaries Forces more crossings
Single row Validates handling of minimal row count
Large widths Ensures no dependence on wall width magnitude
Mixed alignment Verifies counting logic
One row with edge Confirms line may avoid all bricks
Repeated edge positions Tests frequency accumulation

Edge Cases

Rows With Only One Brick

If a row contains exactly one brick, there are no internal boundaries where a line can pass without crossing the brick. A naive implementation might incorrectly include the wall boundary itself as a valid edge.

This implementation avoids the issue by iterating over:

row[:-1]

which excludes the final brick edge entirely.

No Shared Internal Edges

Some walls may have internal boundaries, but none align across rows. In this case every possible vertical line crosses almost every row.

The algorithm handles this naturally because each edge position receives only small frequency counts. The maximum frequency remains low, leading to the correct minimum crossing count.

Empty Edge Map

When every row contains a single brick, the edge map becomes empty because no internal boundaries are added.

Calling max() on an empty collection would normally raise an error. The implementation safely handles this using:

max(edge_count.values(), default=0)

which correctly treats the maximum shared edge count as zero.