Neat Java Solution O(n) using hashmap


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

  • 2
    G

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

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

  • 0
    G

    @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.


  • 1

    @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.


  • 0
    G

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


  • 1
    Y
    This post is deleted!

  • 0
    Y
    This post is deleted!

  • 1

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

  • 0
    G

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


  • 0
    G

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


  • 0
    S

    @GregBoy34 Thanks for the map.merge tip.


Log in to reply
 

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