Java O(n) Hashing Solution


  • 0
    public int leastBricks(List<List<Integer>> wall) {
        int maxGapPoints = 0, width = 0;
        for (Integer i : wall.get(0)) width += i;
        Map<Integer, Integer> map = new HashMap<>();
        for (List<Integer> row : wall) {
            int sum = 0;
            for (Integer i : row) {
                sum += i; 
                Integer curGapFrequency = map.getOrDefault(sum, 0);
                map.put(sum, curGapFrequency+1);
                if (sum != width) maxGapPoints = Math.max(maxGapPoints, curGapFrequency+1);
            }
        }
        return wall.size() - maxGapPoints;
    }
    

Log in to reply
 

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