Python one sweep O(n)


  • 0
        def leastBricks(self, wall):
            if not wall: return 0
            gaps, mx = {}, 0
            for w in wall:
                _sum = 0
                for i in range(len(w)-1):
                    _sum += w[i]
                    gaps[_sum] = gaps.get(_sum,0) + 1
                    mx = max(mx, gaps[_sum])
            return len(wall) - mx
    

  • 0
    A

    @Ellest Can you explain the reasoning behind this approach you have used? Thanks


  • 0

    Basically I'm iterating through each level to find where the gaps are for each level. For example, if a layer is identified as [1,2,3], we can conclude that there are gaps at position 1 and 3 (end points do not count as they define the "wall"). By doing so we have transform this problem into finding the mode of all levels since the mode will represent the position with the most number of gaps and, therefore, the position that will cross the least # of bricks, should we draw a line through the position.


Log in to reply
 

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