# Neat Java Solution O(n) using hashmap

• ``````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;
}
}``````

• 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!

• This post is deleted!

• This post is deleted!

• 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);
}
``````

• @yixuanwang.start I like the guard statement in this.

• I have not bench marked these however it's definitely worth noting for situational purposes

• @GregBoy34 Thanks for the map.merge tip.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.