## Algorithm

Problem Name: 554. Brick Wall

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:

```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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int leastBricks(int** wall, int wallRowSize, int *wallColSizes) {
// in the example, all edges are aligned at:
/* 1.3.5
..34.
1..4.
.2...
..34.
1..45
*/
// the most are at 4
return 4;
}
``````
Copy The Code &

Input

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

Output

cmd
2

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int leastBricks(vector>& wall) {
if(wall.size() == 0 || wall[0].size() == 0) return 0;
unordered_mapm;
for(auto x: wall){
int len = 0;
for(int i = 0; i < x.size() - 1; i++){
len += x[i];
m[len]++;
}
}
int n = wall.size();
int res = n;
for(auto x: m) res = min(res, n - x.second);
return res;
}
};
``````
Copy The Code &

Input

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

Output

cmd
2

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const leastBricks = function(wall) {
const hash = {};
let row;
let rowSum = 0;
for (let i = 0; i < wall.length; i++) {
rowSum = 0;
row = wall[i];
for (let j = 0; j < row.length - 1; j++) {
rowSum += row[j];
hash[rowSum] = hash.hasOwnProperty(rowSum) ? hash[rowSum] + 1 : 1;
}
}
return (
wall.length -
(Object.keys(hash).length > 0
? Math.max(...Object.keys(hash).map(key => hash[key]))
: 0)
);
};

console.log(leastBricks([[1], [1], [1]]));
``````
Copy The Code &

Input

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

Output

cmd
3

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def leastBricks(self, wall: List[List[int]]) -> int:
m = len(wall)
sm = sum(wall[0])
cnt = collections.defaultdict(int)
for i in range(m):
x = 0
for num in wall[i]:
x += num
if x != sm:
cnt[x] += 1
mx = 0
for i in range(m):
x = 0
for num in wall[i]:
x += num
mx = max(mx, cnt[x])
return m - mx
``````
Copy The Code &

Input

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

Output

cmd
3