554. Brick Wall #

Problem #

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 1:

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

Example 2:

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

Constraints:

• n == wall.length
• 1 <= n <= 10^4
• 1 <= wall[i].length <= 10^4
• 1 <= sum(wall[i].length) <= 2 * 10^4
• sum(wall[i]) is the same for each row i.
• 1 <= wall[i][j] <= 2^31 - 1

Problem Summary #

There is a rectangular brick wall in front of you, composed of n rows of bricks. These bricks have the same height (that is, one unit high) but different widths. The sum of the widths of the bricks in each row should be equal. You now need to draw a vertical line from top to bottom that passes through the fewest bricks. If the line you draw only passes along the edge of a brick, it does not count as crossing that brick. You cannot draw the line along either of the two vertical edges of the wall, because that would obviously cross no bricks. You are given a 2D array wall, which contains information about the wall. Here, wall[i] is an array representing the widths of each brick from left to right. You need to determine how to draw the line so that it crosses the fewest bricks, and return the number of bricks crossed.

Solution Approach #

• Since passing through the seams between bricks does not count as crossing bricks, the minimum number of crossed bricks must occur where the line passes through many seams. Iterate through the bricks in each row, accumulate the brick widths in each row, and store the coordinates of each row’s brick “seams” in a map. Finally, find the seam with the highest frequency in the map; this is where the vertical line should pass through. The wall height minus the frequency of that seam is the number of bricks crossed.

Code #

package leetcode

func leastBricks(wall [][]int) int {
	m := make(map[int]int)
	for _, row := range wall {
		sum := 0
		for i := 0; i < len(row)-1; i++ {
			sum += row[i]
			m[sum]++
		}
	}
	max := 0
	for _, v := range m {
		if v > max {
			max = v
		}
	}
	return len(wall) - max
}