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.length1 <= n <= 1041 <= wall[i].length <= 1041 <= sum(wall[i].length) <= 2 * 104sum(wall[i]) is the same for each row i.1 <= wall[i][j] <= 231 - 1Problem Overview: You are given a wall represented as rows of brick widths. The goal is to draw a vertical line from top to bottom that crosses the fewest bricks. If the line passes exactly through the edge between two bricks, it does not count as crossing a brick.
The key observation: crossing fewer bricks means aligning the vertical line with as many brick edges as possible. Every time multiple rows share the same edge position, you avoid crossing those bricks.
Approach 1: Prefix Sum and HashMap (Optimal) (Time: O(N), Space: O(N))
Iterate through each row and compute cumulative brick widths using a prefix sum. Each prefix sum represents a potential edge position where a vertical line could pass. Store the frequency of these edge positions in a HashMap. The last edge in each row is ignored because the line cannot be placed at the wall boundary. The position with the highest frequency means the line passes through the most edges, so the number of crossed bricks becomes rows - maxEdgeFrequency. This approach works efficiently because each brick is processed exactly once, making it linear with respect to the total number of bricks.
This method relies on quick hash lookups to count edge occurrences and is a common technique when solving frequency problems with hash tables. The prefix accumulation step is a direct application of array traversal patterns.
Approach 2: Dynamic Programming Perspective (Time: O(N), Space: O(N))
The same idea can be framed as a dynamic programming accumulation of edge positions. Instead of thinking purely in terms of frequency counting, treat each prefix width as a state representing a candidate cut position. As you iterate row by row, update the count for each position and track the best state seen so far. The "DP state" stores how many rows share that boundary. While the underlying implementation still uses a map, this perspective helps when extending the problem or combining it with other row‑based transitions often seen in dynamic programming.
Compared to brute force attempts that test every possible column position across the wall, this approach avoids scanning the entire width repeatedly. Instead, it only considers natural breakpoints created by brick edges.
Recommended for interviews: The prefix sum + hash map approach is the expected solution. It demonstrates recognition of shared edge boundaries and efficient counting using constant‑time hash lookups. A brute force scan across the wall width shows baseline reasoning, but identifying that edges are the only meaningful positions shows stronger algorithmic insight.
This approach leverages the concept of 'prefix sum' where we keep a running sum across each row to determine the edges of bricks. We use a HashMap to count occurrences of these edges as potential positions to draw a line that crosses the minimum number of bricks.
The provided Python solution employs a defaultdict to accumulate the frequency of edge positions encountered while computing the prefix sum for each brick within the rows. The goal is to find a position with the maximum edge count because this minimizes the number of bricks cut, given that the line will pass through these edges.
Python
Time Complexity: O(m), where m is the total number of bricks. We iterate over each brick except the last one for every row resulting in a time proportional to the number of bricks.
Space Complexity: O(width), where width represents the total width of rows. Edge positions are stored in the map, and their count can scale with the width.
This alternative approach introduces a dynamic programming solution where instead of counting edges, we explore all positions by keeping track of the position sum as a state. The goal is to dynamically compute and avoid unnecessary recomputation of the edge frequencies.
This Java solution exemplifies a similar logic to the Python solution but makes use of Java collections, such as HashMap, to track and update edge counts as the prefix sums are computed. This helps find the cutting position that crosses the fewest bricks.
Java
Time Complexity: O(m), where m is the total number of bricks. This involves iterating through most of the bricks.
Space Complexity: O(width), where width represents the total width of rows. The storage complexity of the HashMap is proportional to how many distinct prefix sums are processed.
The core idea of this approach is to find the vertical line that crosses the least number of bricks by looking at the position where the most number of brick edges align vertically. We can achieve this by computing prefix sums for each row, except for the last brick in each row. A hashmap (or dictionary) is used to keep track of how often each prefix sum occurs.
The C implementation uses an array to simulate a hashmap for counting the number of times a prefix sum occurs. This helps in finding the position with the most edges, which allows determining the vertical line with the least number of bricks crossed.
Time Complexity: O(n * m), where n is the number of rows and m is the average number of bricks per row.
Space Complexity: O(n * m), due to the auxiliary data structure holding prefix sums.
We can use a hash table cnt to record the prefix sum of each row except for the last brick. The key is the value of the prefix sum, and the value is the number of times the prefix sum appears.
Traverse each row, and for each brick in the current row, add it to the current prefix sum and update cnt.
Finally, we traverse cnt to find the prefix sum that appears the most times, which represents the situation where the least number of bricks are crossed. The final answer is the number of rows in the brick wall minus the number of bricks crossed.
The time complexity is O(m times n), and the space complexity is O(n). Here, m and n are the number of rows and the number of bricks in the brick wall, respectively.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Prefix Sum and HashMap | Time Complexity: O(m), where m is the total number of bricks. We iterate over each brick except the last one for every row resulting in a time proportional to the number of bricks. |
| Dynamic Programming Approach | Time Complexity: O(m), where m is the total number of bricks. This involves iterating through most of the bricks. |
| Prefix Sum with HashMap | Time Complexity: O(n * m), where n is the number of rows and m is the average number of bricks per row. |
| Hash Table + Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Vertical Scan | O(W * R) | O(1) | Conceptual baseline when exploring the problem; inefficient for large wall widths. |
| Prefix Sum + HashMap | O(N) | O(N) | General optimal solution; counts edge positions across rows using hash lookups. |
| Dynamic Programming Style Accumulation | O(N) | O(N) | Useful when modeling edge positions as states or extending the problem. |
Brick Wall - Leetcode 554 - Python • NeetCode • 28,537 views views
Watch 9 more video solutions →Practice Brick Wall with our built-in code editor and test cases.
Practice on FleetCode