554. Brick Wall 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        // 穿过的砖块最少即穿过的缝隙最多
        Map<Integer, Integer> gapIndexCountMap = new HashMap<>();

        for (List<Integer> row : wall) {
            int gapIndex = 0;
            for (int i = 0; i < row.size() - 1; i++) {
                gapIndex += row.get(i);
                gapIndexCountMap.put(gapIndex, gapIndexCountMap.getOrDefault(gapIndex, 0) + 1);
            }
        }

        int mostGapIndexCount = 0;
        for (Map.Entry<Integer, Integer> entry : gapIndexCountMap.entrySet()) {
            mostGapIndexCount = Math.max(mostGapIndexCount, entry.getValue());
        }

        return wall.size() - mostGapIndexCount;
    }
}

References

554. Brick Wall