Problem statement

https://leetcode.com/problems/brick-wall/

Solution

It is the same as finding vertical line which crosses maximum number of junctures between bricks. So, we just traverse all bricks in all levels and add frequencies to counter. Also we need to be careful with case, when our counter is empty: it means that we can not put vertical line nowhere in junctures, so we need to put it in the middle of bricks, for example for [[1],[1],[1]] case we can put it in 0.5 place, so total number of crossed bricks is 3. In the end we return total number of layers minus maximum in our counter.

Complexity

Time complexity is O(n), where n is total number of bricks, space complexity as well.

Code

class Solution:
    def leastBricks(self, wall):
        cnt = Counter()
        
        for line in wall:
            for place in list(accumulate(line))[:-1]:
                cnt[place] += 1
                
        return len(wall) - max(cnt.values()) if cnt else len(wall)