Formatted question description: https://leetcode.ca/all/554.html

# 554. Brick Wall (Medium)

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the **top** to the **bottom** and cross the **least** bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

**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. **

**Example:**

Input:[[1,2,2,1], [3,1,2], [1,3,2], [2,4], [3,1,2], [1,3,1,1]]Output:2Explanation:

**Note:**

- The width sum of bricks in different rows are the same and won't exceed INT_MAX.
- The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won't exceed 20,000.

**Companies**:

Bloomberg, Facebook

**Related Topics**:

Hash Table

## Solution 1.

```
// OJ: https://leetcode.com/problems/brick-wall
// Time: O(N)
// Space: O(W) where W is the width of wall
class Solution {
public:
int leastBricks(vector<vector<int>>& wall) {
int maxCnt = 0;
unordered_map<int, int> cnt;
for (auto row : wall)
for (int i = 0, w = 0; i < row.size() - 1; ++i)
maxCnt = max(maxCnt, ++cnt[w += row[i]]);
return wall.size() - maxCnt;
}
};
```

Java

```
class Solution {
public int leastBricks(List<List<Integer>> wall) {
if (wall == null || wall.size() == 0)
return 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (List<Integer> row : wall) {
int curWidth = 0;
int size = row.size() - 1;
for (int i = 0; i < size; i++) {
int width = row.get(i);
curWidth += width;
int count = map.getOrDefault(curWidth, 0);
count++;
map.put(curWidth, count);
}
}
int maxEdges = 0;
Set<Integer> keySet = map.keySet();
for (int key : keySet) {
int count = map.getOrDefault(key, 0);
maxEdges = Math.max(maxEdges, count);
}
int minCrossBricks = wall.size() - maxEdges;
return minCrossBricks;
}
}
```