How do you solve Brick Wall on LeetCode?

Brick Wall (LeetCode #554) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The edges between bricks are crucial for determining where to draw the line.

What is the brute force solution for Brick Wall?

The brute force approach for Brick Wall is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every possible vertical line position and counting how many bricks are crossed. This is straightforward but inefficient, as it requires checking each row for every possible line position. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Brick Wall?

Brick Wall uses the following concepts: Array, Hash Table. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Brick Wall?

Always think about how to optimize a brute-force solution — look for patterns or structures in the data. Explain your thought process clearly; interviewers appreciate understanding your reasoning. Practice edge cases, such as walls with varying numbers of bricks in each row.

What are common mistakes when solving Brick Wall?

Failing to account for the last brick in each row when calculating edge positions. Not using a HashMap or similar structure to track edge counts, leading to unnecessary complexity.

#554

Brick Wall

Medium

ArrayHash TableHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a HashMap to track the number of edges (or gaps) between bricks for each possible vertical line position. By finding the position with the most edges, we can minimize the number of crossed bricks.

⚙️

Algorithm

3 steps

1Step 1: Initialize a HashMap to count the number of edges at each position.
2Step 2: For each row, calculate the edge positions and update the HashMap.
3Step 3: The maximum value in the HashMap indicates the most edges crossed, so subtract this from the total number of rows to get the minimum crossed bricks.

solution.py13 lines

1# Full working Python code
2from collections import defaultdict
3
4def leastBricks(wall):
5    edge_count = defaultdict(int)
6    for row in wall:
7        position = 0
8        for brick in row[:-1]:  # Exclude the last brick
9            position += brick
10            edge_count[position] += 1
11    return len(wall) - max(edge_count.values(), default=0)
12
13print(leastBricks([[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]))

ℹ

Complexity note: The time complexity is O(n) because we only traverse each row once to calculate edge positions, leading to linear growth with respect to the number of rows.

1The edges between bricks are crucial for determining where to draw the line.
2Using a HashMap allows us to efficiently count the edges and minimize crossed bricks.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.