class Solution { public int leastBricks(List<List<Integer>> wall) { //make a frequency map of number of splits against index //whichever index will have maximum split against it , crossing a line //from that index will cut minimum no. of bricks //minimum no. bricks = maximum no. of splits in wall //make prefix sum as we are just given the width and we need index HashMap<Integer,Integer> map = new HashMap<>(); int ans = 0 ; for(int i = 0 ; i < wall.size(); i++){ List<Integer> col = wall.get(i); int psum = 0; //prefix sum //prefix sum will start from 0 after completing every coloumn for(int j = 0 ; j < col.size();j++){ psum += col.get(j); //put split against the index,do not consider last wall if(j != col.size()-1) map.put(psum,map.getOrDefault(psum,0)+1); } } //iterate through the hashmap and store the index with maximum split //max can also be found while updating frequency for(int idx : map.keySet()) ans = Math.max(ans,map.get(idx)); //ans = total bricks - max gaps //if ans stays 0 that means all bricks are same size return wall.size() - ans; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter