Java linear solution using hash Map. Beats 99.50%


  • 0
    M

    Basically, the idea is find the sum of width at each brick at each row of the wall. The maximum number of rows having same sum at some point is the point where we want to draw the line.

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

Log in to reply
 

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