## Brick Wall

• Time:O(n), where n = |\text{bricks}|
• Space:Space:

## C++

class Solution {
public:
int leastBricks(vector<vector<int>>& wall) {
int maxCount = 0;
unordered_map<int, int> count;

for (const auto& row : wall) {
int prefix = 0;
for (int i = 0; i < row.size() - 1; ++i) {
prefix += row[i];
maxCount = max(maxCount, ++count[prefix]);
}
}

return wall.size() - maxCount;
}
};


## JAVA

class Solution {
public int leastBricks(List<List<Integer>> wall) {
int maxFreq = 0;
Map<Integer, Integer> count = new HashMap<>();

for (List<Integer> row : wall) {
int prefix = 0;
for (int i = 0; i < row.size() - 1; ++i) {
prefix += row.get(i);
count.put(prefix, count.getOrDefault(prefix, 0) + 1);
maxFreq = Math.max(maxFreq, count.get(prefix));
}
}

return wall.size() - maxFreq;
}
}


## Python

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

for row in wall:
prefix = 0
for i in range(len(row) - 1):
prefix += row[i]
count[prefix] += 1
maxFreq = max(maxFreq, count[prefix])

return len(wall) - maxFreq