LeetCode-Solutions/Python/brick-wall.py at master · pythonpeixun/LeetCode-Solutions · GitHub

22 lines (18 loc) · 579 Bytes

# Time: O(n), n is the total number of the bricks

# Space: O(m), m is the total number different widths

import collections

class Solution(object):

def leastBricks(self, wall):

"""

:type wall: List[List[int]]

:rtype: int

"""

widths = collections.defaultdict(int)

result = len(wall)

for row in wall:

width = 0

for i in xrange(len(row)-1):

width += row[i]

widths[width] += 1

result = min(result, len(wall) - widths[width])

return result

Expand file tree