# Brick Wall
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/brick-wall)
Canonical: https://scaleengineer.com/dsa/problems/brick-wall
**Data structures:** Array, Hash Table
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [Trexquant](https://scaleengineer.com/companies/trexquant)
---
## 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. The total width of each row is the same.

Draw a vertical line from the top to the bottom and cross the least bricks. If your line goes through the edge of a brick, then the brick is not considered as crossed. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Given the 2D array `wall` that contains the information about the wall, return _the minimum number of crossed bricks after drawing such a vertical line_.

**Example 1:**

![](https://assets.glich.co/dsa/brick-wall/image0.png) 

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

**Example 2:**

**Input:** wall = [[1],[1],[1]]
**Output:** 3

**Constraints:**

* `n == wall.length`
* `1 <= n <= 104`
* `1 <= wall[i].length <= 104`
* `1 <= sum(wall[i].length) <= 2 * 104`
* `sum(wall[i])` is the same for each row `i`.
* `1 <= wall[i][j] <= 231 - 1`

# Approaches
## Brute Force by Checking All Positions
This approach exhaustively checks every possible vertical line position. It iterates from 1 to the total width of the wall minus one. For each position, it manually counts how many bricks would be crossed by iterating through every brick in every row. The minimum count found across all positions is the result.
**Time:** O(W * N), where `W` is the total width of the wall and `N` is the total number of bricks. This is because the outer loop runs `W-1` times, and inside it, we may iterate through all `N` bricks in the worst case. · **Space:** O(1), as it only uses a few variables to keep track of counts and positions, regardless of the input size.
**Pros:** Simple to conceptualize and implement.; Requires minimal extra space (O(1)).
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.; The performance is heavily dependent on the total width of the wall, which can be very large.
### Explanation
The brute-force method relies on a straightforward simulation. Since the brick widths are integers, the number of crossed bricks can only change at integer coordinates. Therefore, we only need to test vertical lines at integer positions `p` from `1` to `width - 1`.

For each potential line position `p`, we perform a check across all rows of the wall. For each row, we lay out the bricks conceptually from left to right, keeping track of the current position. We check if our line `p` intersects with any of the bricks. An intersection occurs if `p` is greater than the starting edge of a brick but less than or equal to its ending edge. If an intersection is found, we increment a counter for the current line position `p` and move on to the next row, as a single line can only cross one brick per row.

After checking all rows for a given `p`, we compare the total crossings with a global minimum, updating it if necessary. This process is repeated for all possible line positions.

```java
import java.util.List;

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int numRows = wall.size();
        if (numRows == 0) {
            return 0;
        }

        long wallWidth = 0;
        for (int width : wall.get(0)) {
            wallWidth += width;
        }

        // If width is 1, no valid line can be drawn, so all bricks are crossed.
        if (wallWidth == 1) {
            return numRows;
        }

        int minCrossed = numRows;

        // Iterate through all possible vertical line positions (excluding edges).
        for (long pos = 1; pos < wallWidth; pos++) {
            int currentCrossed = 0;
            for (List<Integer> row : wall) {
                long currentPos = 0;
                for (int brickWidth : row) {
                    // Check if the line at 'pos' crosses the current brick.
                    if (currentPos < pos && pos <= currentPos + brickWidth) {
                        currentCrossed++;
                        break; // Move to the next row.
                    }
                    currentPos += brickWidth;
                }
            }
            minCrossed = Math.min(minCrossed, currentCrossed);
        }
        return minCrossed;
    }
}
```
### Algorithm
- Calculate the total width `W` of the wall by summing the brick widths in the first row.
- Initialize `min_crossings` to the total number of rows, `n`.
- Iterate through every possible integer coordinate `p` from 1 to `W-1`.
- For each `p`, initialize a counter `current_crossings` to 0.
- For each `row` in the wall:
  - Keep a running sum of brick widths, `position_sum`.
  - Iterate through the bricks in the row.
  - If the line at `p` falls within the current brick's boundaries (i.e., `position_sum < p <= position_sum + brick_width`), increment `current_crossings` and move to the next row.
  - Update `position_sum`.
- After checking all rows for position `p`, update `min_crossings = min(min_crossings, current_crossings)`.
- Return `min_crossings` after checking all possible positions.

## Optimized Approach using Hash Map
This optimized approach cleverly transforms the problem. Instead of minimizing the number of crossed bricks, it focuses on maximizing the number of brick edges that a single vertical line can pass through. If a line passes through an edge, it doesn't cross a brick in that row. By finding the edge position that occurs most frequently across all rows, we find the best place to draw the line. The final answer is the total number of rows minus this maximum frequency.
**Time:** O(N), where `N` is the total number of bricks in the wall. This is because we iterate through each brick exactly once to calculate its edge position and update the map. · **Space:** O(M), where `M` is the number of unique internal edge positions. In the worst-case scenario, where every edge position is unique, the space complexity is proportional to the total number of bricks, `N`. So, it's O(N).
**Pros:** Optimal time complexity, as it processes each brick only once.; Directly computes the best possible outcome without unnecessary checks.
**Cons:** Requires extra space to store the edge frequencies, which can be proportional to the total number of bricks in the worst case.
### Explanation
The most efficient solution is based on the insight that the optimal line must align with as many brick edges as possible. Each edge represents an opportunity to pass through a row without crossing a brick.

We can use a Hash Map to count the occurrences of each edge position. We iterate through every row of the wall. For each row, we calculate the positions of the internal edges by maintaining a running sum of brick widths. The final edge of each row (the right boundary of the wall) is ignored, as per the problem's constraints.

For each calculated edge position, we increment its corresponding count in the hash map. While doing this, we also keep track of the maximum count seen so far (`maxEdges`). This `maxEdges` value represents the maximum number of rows that a single vertical line can pass through without crossing any bricks.

If every row consists of a single brick, there will be no internal edges, and `maxEdges` will remain 0. In this case, any line must cross all bricks.

Finally, the minimum number of bricks to cross is the total number of rows minus the maximum number of aligned edges (`numRows - maxEdges`).

```java
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        // Map to store frequency of each edge position
        Map<Integer, Integer> edgeCounts = new HashMap<>();
        int maxEdges = 0;
        int numRows = wall.size();

        for (List<Integer> row : wall) {
            int position = 0;
            // Iterate through the bricks of a row to find edge positions
            // We don't consider the last brick's edge as it's the wall's boundary
            for (int i = 0; i < row.size() - 1; i++) {
                position += row.get(i);
                int count = edgeCounts.getOrDefault(position, 0) + 1;
                edgeCounts.put(position, count);
                // Keep track of the maximum number of aligned edges
                maxEdges = Math.max(maxEdges, count);
            }
        }

        // The number of crossed bricks is the total rows minus the rows that the line can pass through via edges.
        return numRows - maxEdges;
    }
}
```
### Algorithm
- The problem can be rephrased as finding a vertical line that passes through the maximum number of brick edges.
- Initialize a Hash Map, `edgeCounts`, to store the frequency of each edge position.
- Initialize `maxEdges = 0` to track the maximum number of aligned edges found so far.
- Iterate through each `row` of the `wall`.
  - For each row, maintain a `position` sum, initialized to 0.
  - Iterate through the bricks in the current row, but stop before the last brick (as we cannot draw a line on the wall's outer edge).
  - Add the current `brick_width` to `position` to find the location of the next edge.
  - Increment the count for this `position` in the `edgeCounts` map.
  - Update `maxEdges = max(maxEdges, new_count_for_position)`.
- The minimum number of bricks crossed is the total number of rows minus `maxEdges`.

# Solutions
### Java

```java
class Solution { public int leastBricks ( List < List < Integer >> wall ) { Map < Integer , Integer > cnt = new HashMap <>(); for ( List < Integer > row : wall ) { int width = 0 ; for ( int i = 0 , n = row . size () - 1 ; i < n ; i ++) { width += row . get ( i ); cnt . merge ( width , 1 , Integer: : sum ); } } int max = cnt . values (). stream (). max ( Comparator . naturalOrder ()). orElse ( 0 ); return wall . size () - max ; } }
```

### JavaScript

```javascript
/** * @param {number[][]} wall * @return {number} */ var leastBricks =
  function (wall) {
    const cnt = new Map();
    for (const row of wall) {
      let width = 0;
      for (let i = 0, n = row.length - 1; i < n; ++i) {
        width += row[i];
        cnt.set(width, (cnt.get(width) || 0) + 1);
      }
    }
    let max = 0;
    for (const v of cnt.values()) {
      max = Math.max(max, v);
    }
    return wall.length - max;
  };

```

### Python

```python
class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int: cnt = defaultdict(int) for row in wall: width = 0 for brick in row[: - 1]: width += brick cnt[width] += 1 if not cnt: return len(wall) return len(wall) - cnt[max(cnt, key=cnt . get)]

```

### CPP

```cpp
class Solution { public: int leastBricks ( vector < vector < int >>& wall ) { unordered_map < int , int > cnt ; for ( const auto & row : wall ) { int s = 0 ; for ( int i = 0 ; i + 1 < row . size (); ++ i ) { s += row [ i ]; cnt [ s ] ++ ; } } int mx = 0 ; for ( const auto & [ _ , x ] : cnt ) { mx = max ( mx , x ); } return wall . size () - mx ; } };
```