public class Solution {
public int leastBricks(List < List < Integer >> wall) {
HashMap < Integer, Integer > map = new HashMap < > ();
for (List < Integer > row: wall) {
int sum = 0;
for (int i = 0; i < row.size()  1; i++) {
sum += row.get(i);
if (map.containsKey(sum))
map.put(sum, map.get(sum) + 1);
else
map.put(sum, 1);
}
}
int res = wall.size();
for (int key: map.keySet())
res = Math.min(res, wall.size()  map.get(key));
return res;
}
}
Neat Java Solution O(n) using hashmap


I havent tested performance, but you can also replace
for (int i = 0; i < row.size()  1; i++) { sum += row.get(i); if (map.containsKey(sum)) map.put(sum, map.get(sum) + 1); else map.put(sum, 1); }
With the merge method in Java 8
for (int i = 0; i < row.size()  1; i++) { sum += row.get(i); map.merge(sum, 1, Integer::sum); }

public int leastBricks(List<List<Integer>> wall) { Map<Long, Integer> gaps = new HashMap<>(); int maxGaps = 0; for(List<Integer> row : wall) { long sum = 0; for(int i = 0; i < row.size()  1; i++) { sum += row.get(i); gaps.put(sum, gaps.getOrDefault(sum, 0) + 1); maxGaps = Math.max(maxGaps, gaps.get(sum)); } } return wall.size()  maxGaps; }

@jaqenhgar In this solution is it possible that as you iterate through the rows
of the wall and store the value in the hash map that you could have a scenario where
you are putting two of the same values into the map, hence only one is added? I also
am curious if using a long here is based on the question requirements or for efficiency.

@GregBoy34 To your first question, no  If the
sum
already exists in map from previous rows, I'm incrementing it by 1. And if you meant the same row, then it'll never have the same sum since brick width can't be zero.Also use of long is just to avoid overflow, but I realized the question mentions that the sum doesn't overflow.

@jaqenhgar Thank you it is a nice robust solution. I would look at how much input this is expecting as it might be more practical to use an int or even a short.. In this situation, safety first!

Using streams:
public int leastBricks(List<List<Integer>> wall) { Map<Integer, Integer> gaps = new HashMap<>(); for (List<Integer> line : wall) for (int i = 0, sum = 0; i + 1 < line.size(); i++) { sum += line.get(i); gaps.put(sum, gaps.getOrDefault(sum, 0) + 1); } return wall.size()  gaps.values().stream().mapToInt(i>i).max().orElse(0); }

