Short Java O(n) Solution explained


  • 0
    Q

    Key point: the position for vertical line to cross the least bricks = the position for the most bricks end

    public int leastBricks(List<List<Integer>> wall) {
            int maxtime = -1, width = 0;
            for(Integer i : wall.get(0)) width += i;
    		HashMap<Integer, Integer> map = new HashMap();
    		for(List<Integer> l : wall) {
            	int sum = 0;
            	for(Integer i : l) {
            		sum += i;
            		if(sum == width) break;
            		if(map.containsKey(sum)) map.put(sum, map.get(sum) + 1);
            		else map.put(sum, 1);
            		if(map.get(sum) > maxtime) maxtime = map.get(sum);
            	}
            }
            if(maxtime == -1) return wall.size();
            return wall.size() - maxtime;
        }
    

Log in to reply
 

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