Python solution with detailed explanation


  • 0
    G

    Solution

    Brick Wall https://leetcode.com/problems/brick-wall/#/description

    Optimized Approach

    • Create a hash-table with key as a potential brick edge and value as a set of rows which share that edge.
    • How do we get a potential brick edge? Consider row (0) = [1,2,2,1], the edges are 1,3,5,6. So we add all these edges as keys to the cache. The value set will have row 0. Repeat the process for all rows. Note we would not want to add edge 6 (the final boundary) just like we dont want to add edge 0 - it is a common edge for all lines.
    • Now we would want the line to pass through atleast one edge. Therefore the potential start points for the line are the keys in the cache. How many bricks will a line with a start point st cross? Answer: len(wall) - the rows where it is an edge. The latter can be answered from the cache we developed in the previous step.
    from collections import defaultdict        
    class Solution(object):
        def leastBricks(self, wall):
            """
            :type wall: List[List[int]]
            :rtype: int
            """
            if wall == []:
                return 0
            cache, csum, min_so_far = defaultdict(set), 0, len(wall)
            for idx, row in enumerate(wall):
                csum = 0
                for x in row:
                    csum += x
                    cache[csum].add(idx)
            del cache[csum]
            for st in cache.keys():
                min_so_far = min(min_so_far, len(wall)-len(cache[st]))
            return min_so_far
    

Log in to reply
 

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