LC554. Brick Wall

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        """
        tc O(NM)  sc O(L) N: len of wall ;  M: max len of each row ;  L : number of unique accuemutive sum  
        main idea: break least bricks means for each list, presum at each point freq is the most    
        1. create dictionary to record freq of each list's accumutive sum 
        2. find the most freq 
        3. len of lst - most freq 
        
        """
        max_frq = 0
        d = {}
        for w in wall:
            sum_b = 0
            for x in w[:-1]:  # avoid last brick since the sum is the same 
                sum_b += x
                d[sum_b] = d.get(sum_b,0) + 1 
                max_frq = max(max_frq,d[sum_b])
        return len(wall) - max_frq