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 = Integer.MIN_VALUE ;

        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
        for(int idx : map.keySet())
            ans = Math.max(ans,map.get(idx));
        
            
            //ans  = total bricks - max gaps
            //if ans stays default value that means all bricks are same size
            return ans == Integer.MIN_VALUE ? wall.size() : wall.size() - ans;
        
    }
}