554. Brick Wall

Problem Statement

link: LeetCode.cn LeetCode There is a rectangular brick wall in front of you with n rows of bricks. The ith row has some number of bricks each of the same height (i.e., one unit) but they can be of different widths. The total width of each row is the same.

Draw a vertical line from the top to the bottom and cross the least bricks. If your line goes through the edge of a brick, then the brick is not considered as crossed. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Given the 2D array wall that contains the information about the wall, return the minimum number of crossed bricks after drawing such a vertical line.

Example:

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]] Output: ` 2`

Input: wall = [[1],[1],[1]] Output: 3

Constraints: n == wall.length 1 <= n <= 104 1 <= wall[i].length <= 104 1 <= sum(wall[i].length) <= 2 * 104 sum(wall[i]) is the same for each row i. 1 <= wall[i][j] <= 231 - 1

Solution Approach

The solution involves tracking the number of brick edges at each possible column and finding the column where the fewest bricks are crossed by subtracting the maximum edge count from the total number of rows.

Algorithm

1. Track Brick Edges: Iterate through each row of the wall, summing the widths of bricks to track the positions of edges using a dictionary.
2. Count Edge Occurrences: For each brick edge (excluding the last brick in each row), increment the corresponding position in the dictionary to count how many rows have an edge at that position.
3. Determine Minimum Crossed Bricks: Find the maximum value in the dictionary (representing the column with the most edges) and subtract it from the total number of rows to get the minimum number of bricks crossed by the vertical line.

Implement

    class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        dic = defaultdict(int) #{col: breaks}
        for row in wall:
            tmp = 0 # track the column index
            for c in row[:-1]:# not include the final one 
                tmp += c
                dic[tmp] += 1
        if len(dic) == 0:
            return len(wall)
        return len(wall) - max(dic.values())

    
    

Twitter  facebook  Email