Brick Wall
MedPrompt
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: 2Example 2:
Input: wall = [[1],[1],[1]]
Output: 3
Constraints:
n == wall.length1 <= n <= 1041 <= wall[i].length <= 1041 <= sum(wall[i].length) <= 2 * 104sum(wall[i])is the same for each rowi.1 <= wall[i][j] <= 231 - 1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach exhaustively checks every possible vertical line position. It iterates from 1 to the total width of the wall minus one. For each position, it manually counts how many bricks would be crossed by iterating through every brick in every row. The minimum count found across all positions is the result.
Algorithm
- Calculate the total width
Wof the wall by summing the brick widths in the first row. - Initialize
min_crossingsto the total number of rows,n. - Iterate through every possible integer coordinate
pfrom 1 toW-1. - For each
p, initialize a countercurrent_crossingsto 0. - For each
rowin the wall:- Keep a running sum of brick widths,
position_sum. - Iterate through the bricks in the row.
- If the line at
pfalls within the current brick's boundaries (i.e.,position_sum < p <= position_sum + brick_width), incrementcurrent_crossingsand move to the next row. - Update
position_sum.
- Keep a running sum of brick widths,
- After checking all rows for position
p, updatemin_crossings = min(min_crossings, current_crossings). - Return
min_crossingsafter checking all possible positions.
Walkthrough
The brute-force method relies on a straightforward simulation. Since the brick widths are integers, the number of crossed bricks can only change at integer coordinates. Therefore, we only need to test vertical lines at integer positions p from 1 to width - 1.
For each potential line position p, we perform a check across all rows of the wall. For each row, we lay out the bricks conceptually from left to right, keeping track of the current position. We check if our line p intersects with any of the bricks. An intersection occurs if p is greater than the starting edge of a brick but less than or equal to its ending edge. If an intersection is found, we increment a counter for the current line position p and move on to the next row, as a single line can only cross one brick per row.
After checking all rows for a given p, we compare the total crossings with a global minimum, updating it if necessary. This process is repeated for all possible line positions.
import java.util.List; class Solution { public int leastBricks(List<List<Integer>> wall) { int numRows = wall.size(); if (numRows == 0) { return 0; } long wallWidth = 0; for (int width : wall.get(0)) { wallWidth += width; } // If width is 1, no valid line can be drawn, so all bricks are crossed. if (wallWidth == 1) { return numRows; } int minCrossed = numRows; // Iterate through all possible vertical line positions (excluding edges). for (long pos = 1; pos < wallWidth; pos++) { int currentCrossed = 0; for (List<Integer> row : wall) { long currentPos = 0; for (int brickWidth : row) { // Check if the line at 'pos' crosses the current brick. if (currentPos < pos && pos <= currentPos + brickWidth) { currentCrossed++; break; // Move to the next row. } currentPos += brickWidth; } } minCrossed = Math.min(minCrossed, currentCrossed); } return minCrossed; }}Complexity
Time
O(W * N), where `W` is the total width of the wall and `N` is the total number of bricks. This is because the outer loop runs `W-1` times, and inside it, we may iterate through all `N` bricks in the worst case.
Space
O(1), as it only uses a few variables to keep track of counts and positions, regardless of the input size.
Trade-offs
Pros
Simple to conceptualize and implement.
Requires minimal extra space (O(1)).
Cons
Extremely inefficient and will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
The performance is heavily dependent on the total width of the wall, which can be very large.
Solutions
Solution
class Solution { public int leastBricks ( List < List < Integer >> wall ) { Map < Integer , Integer > cnt = new HashMap <>(); for ( List < Integer > row : wall ) { int width = 0 ; for ( int i = 0 , n = row . size () - 1 ; i < n ; i ++) { width += row . get ( i ); cnt . merge ( width , 1 , Integer: : sum ); } } int max = cnt . values (). stream (). max ( Comparator . naturalOrder ()). orElse ( 0 ); return wall . size () - max ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.