Easy Python with dictionary

  • 0

    Brute Force way

    My first idea was to go through each column of the whole wall, but it would lead to TLE, since the length of a brick could be very huge:

    class Solution(object):
        def leastBricks(self, wall):
            least = len(wall)
            while wall[0] and not (wall[0][0] == 1 and len(wall[0]) == 1):
                count = 0
                for row in wall:
                    if row[0] == 1:
                        row[0] -= 1
                        count += 1
                least = min(least, count)
            return least

    Using hashtable

    Then I realized I only needed to count the occurrence of each brick space and used the height of wall to subtract the max occurrence of the space

    class Solution(object):
        def leastBricks(self, wall):
            spaceMap = dict()
            for row in wall:
                spacelen = 0
                for brick in row[:-1]: # avoid counting wall edge
                    spacelen += brick
                    if spacelen not in spaceMap:
                        spaceMap[spacelen] = 1
                        spaceMap[spacelen] += 1
            least = len(wall) - max(spaceMap.values())
            return least

    Time Complexity: O(n), n for number of bricks
    Space Complexity: O(n)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.