# LeetCode 554: Brick Wall

## Problem Restatement

We are given a rectangular brick wall.

The wall has several rows. Each row contains bricks of different widths, but every row has the same total width.

We need to draw one vertical line from the top of the wall to the bottom.

If the line passes through the middle of a brick, it crosses that brick.

If the line passes exactly through the edge between two bricks, it does not cross a brick in that row.

We cannot draw the line along the far left or far right edge of the wall.

Return the minimum number of bricks the vertical line must cross.

The important rule is that a line through a brick edge is free for that row. So we want to place the line where the most brick edges line up. The problem statement and constraints specify that all rows have the same total width, and the total number of bricks is at most `20000`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `wall`, a list of rows |
| Row | A list of brick widths from left to right |
| Output | Minimum number of crossed bricks |
| Forbidden line | The far left edge and far right edge of the wall |

Example function shape:

```python
def leastBricks(wall: list[list[int]]) -> int:
    ...
```

## Examples

Example:

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

All rows have total width `6`.

Now look at the internal brick edges.

For the first row:

```python
[1, 2, 2, 1]
```

The internal edge positions are:

```python
1
1 + 2 = 3
1 + 2 + 2 = 5
```

We do not include position `6`, because that is the right wall edge.

For all rows, the internal edge positions are:

| Row | Bricks | Internal edge positions |
|---|---|---|
| 1 | `[1, 2, 2, 1]` | `1, 3, 5` |
| 2 | `[3, 1, 2]` | `3, 4` |
| 3 | `[1, 3, 2]` | `1, 4` |
| 4 | `[2, 4]` | `2` |
| 5 | `[3, 1, 2]` | `3, 4` |
| 6 | `[1, 3, 1, 1]` | `1, 4, 5` |

The edge counts are:

| Position | Number of rows with an edge there |
|---|---|
| `1` | `3` |
| `2` | `1` |
| `3` | `3` |
| `4` | `4` |
| `5` | `2` |

The best position is `4`, where four rows have a brick edge.

There are six rows total, so the line crosses:

```python
6 - 4 = 2
```

bricks.

So the answer is:

```python
2
```

## First Thought: Try Every Vertical Position

One direct idea is to try every possible vertical position inside the wall.

For each position, count how many rows do not have an edge there. Those rows are crossed by the line.

This is logically correct, but it can be too slow because the wall width can be large. Brick widths are integers, and the total width can be much larger than the number of bricks.

We should not iterate over every coordinate. We only care about coordinates where brick edges occur.

## Key Insight

A vertical line crosses fewer bricks when it passes through more internal brick edges.

So instead of counting crossed bricks directly, count aligned edges.

If a line is placed at position `x` and `k` rows have an internal edge at `x`, then the line does not cross those `k` rows.

If the wall has `h` rows, then the line crosses:

```python
h - k
```

bricks.

To minimize crossed bricks, maximize `k`.

So the answer is:

```python
number_of_rows - maximum_edge_frequency
```

We must ignore the final edge of each row, because drawing along the right boundary is not allowed.

## Algorithm

Create a hash map called `edge_count`.

For each row:

1. Start with `position = 0`.
2. Iterate through every brick except the last brick.
3. Add the brick width to `position`.
4. Increment `edge_count[position]`.

After processing all rows:

1. Find the largest value in `edge_count`.
2. Return `len(wall) - largest_value`.

If there are no internal edges, then `edge_count` is empty. That means every row has exactly one brick. Any valid vertical line crosses every row, so the answer is `len(wall)`.

## Correctness

Each internal edge position represents a place where a vertical line can pass through a gap in that row.

For a fixed vertical position `x`, suppose `edge_count[x] = k`. That means exactly `k` rows have a brick edge at `x`. In those rows, the line crosses no brick. In all other rows, the line must pass through the interior of some brick, because every row covers the full wall width.

Therefore, drawing the line at `x` crosses exactly:

```python
len(wall) - edge_count[x]
```

bricks.

The optimal line must be placed at an internal edge position if it wants to avoid crossing at least one row. If a line is placed at a position with no internal edge, then it crosses every row. Such a position cannot be better than the most frequent internal edge position, unless no internal edge exists at all.

The algorithm counts every allowed internal edge position and chooses the position with the largest frequency. Therefore, it maximizes the number of rows avoided and minimizes the number of bricks crossed.

## Complexity

Let `m` be the total number of bricks in the wall.

| Metric | Value | Why |
|---|---|---|
| Time | `O(m)` | We process each brick at most once |
| Space | `O(m)` | The hash map can store many distinct edge positions |

## Implementation

```python
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:
            position = 0

            for width in row[:-1]:
                position += width
                edge_count[position] += 1

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

        return len(wall) - max_edges
```

## Code Explanation

We use a hash map:

```python
edge_count = defaultdict(int)
```

The key is an internal edge position.

The value is how many rows have an edge at that position.

For each row, we compute prefix sums:

```python
position = 0

for width in row[:-1]:
    position += width
    edge_count[position] += 1
```

The slice `row[:-1]` is important.

It skips the last brick, because after the last brick we reach the right edge of the wall. The problem does not allow drawing the line along the wall boundary.

After all rows are processed, we find the largest number of aligned edges:

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

The `default=0` handles the case where every row has only one brick.

Finally:

```python
return len(wall) - max_edges
```

The total number of rows minus the largest number of avoided rows gives the minimum number of crossed bricks.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.leastBricks([
        [1, 2, 2, 1],
        [3, 1, 2],
        [1, 3, 2],
        [2, 4],
        [3, 1, 2],
        [1, 3, 1, 1],
    ]) == 2

    assert s.leastBricks([[1], [1], [1]]) == 3
    assert s.leastBricks([[1, 1], [1, 1], [1, 1]]) == 0
    assert s.leastBricks([[2, 3], [1, 4], [3, 2]]) == 2
    assert s.leastBricks([[1, 2, 1], [2, 2], [3, 1]]) == 1

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Main sample wall | Checks normal aligned-edge counting |
| `[[1], [1], [1]]` | No internal edges, must cross every row |
| `[[1, 1], [1, 1], [1, 1]]` | All rows have the same internal edge |
| `[[2, 3], [1, 4], [3, 2]]` | No shared best edge beyond one row |
| `[[1, 2, 1], [2, 2], [3, 1]]` | Multiple different prefix positions |