# 0554. Brick Wall
###### tags: `Leetcode` `Bloomberg` `Medium`
Link: https://leetcode.com/problems/brick-wall/
## 思路
**O(N) O(M) N是brick的个数 M是map里面key的个数，也就是墙的宽度**
prefix sum算出每个brick结束的位置之后，用hashmap记录所有层的brick结束的各个位置
We will never obtain the same value of sumsum twice while traversing over a particular row. Thus, if the sum value is repeated while traversing over the rows, it means some row's brick boundary coincides with some previous row's brick boundary.
But, for every row, we consider the sum only up to the second last brick, since the last boundary isn't a valid boundary for the solution.
最后我们只要找到出现次数最多的key，墙的总高度-出现次数最多的key出现的次数就是答案
## Code

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0;i < wall.size();i++){
            int sum = 0;
            for(int j = 0;j < wall.get(i).size()-1;j++){
                sum += wall.get(i).get(j);
                map.put(sum, map.getOrDefault(sum, 0)+1);
            }
        }
        int ans = wall.size();
        for(int num:map.keySet()){
            ans = Math.min(ans, wall.size()-map.get(num));
        }
        return ans;
    }
}