Skip to main content
Talentd

Brick Wall - Solution & Explanation

MediumArrayHash Table16 min readAsked at: Amazon, Meta, KLA +2
Practice this problem

Problem Statement

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 <= 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

Approach Overview

Problem 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.

Approach 1: Prefix Sum and HashMap

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.

Code

Python

Python

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

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.

Code

Java

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Prefix Sum with HashMap

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 4: Hash Table + Prefix Sum

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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
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.

Dynamic Programming Approach

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.

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.
Space Complexity: O(n * m), due to the auxiliary data structure holding prefix sums.

Hash Table + Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Vertical ScanO(W * R)O(1)Conceptual baseline when exploring the problem; inefficient for large wall widths.
Prefix Sum + HashMapO(N)O(N)General optimal solution; counts edge positions across rows using hash lookups.
Dynamic Programming Style AccumulationO(N)O(N)Useful when modeling edge positions as states or extending the problem.

Video Solution

Brick Wall - Leetcode 554 - Python • NeetCode • 28,965 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Brick Wall easy or hard?
Brick Wall is typically classified as a Medium problem. The challenge is recognizing that the optimal cut must align with brick edges and that counting these edges across rows leads to a linear-time solution.
Brick Wall Python/Java solution
In Python or Java, iterate through each row, maintain a running prefix sum, and update a hash map that stores edge frequencies. Skip the last brick in every row to avoid counting the wall boundary. After processing all rows, subtract the maximum frequency from the number of rows to get the minimum bricks crossed.
How to solve Brick Wall in O(n)?
Compute the cumulative width of bricks in each row using prefix sums and store each edge position in a hash map. Ignore the last edge because it represents the wall boundary. The edge position with the highest frequency indicates where the vertical line crosses the fewest bricks. The result equals rows minus that frequency.
What is the best approach for Brick Wall?
The optimal solution uses prefix sums with a hash map to count how often brick edges align across rows. Each prefix sum represents an edge position. The vertical line should pass through the edge that appears most frequently. The final answer is total rows minus the maximum edge frequency, with overall time complexity O(N).
Is Brick Wall asked at Google/Amazon/Meta?
Brick Wall is a common interview-style problem focused on prefix sums and hash maps. Variants of this pattern appear in interviews at companies like Amazon and Google where candidates must detect shared boundaries or frequency of positions efficiently.
What data structure is used in Brick Wall?
A hash map is the primary data structure used to count how many rows share the same brick edge position. Prefix sums are computed while iterating through each row of the array representing the wall. This combination allows constant-time updates and fast frequency tracking.
What is the time complexity of Brick Wall?
The optimal prefix sum and hash map approach runs in O(N) time, where N is the total number of bricks in the wall. Each brick contributes once to a prefix sum calculation and a hash map update. Space complexity is also O(N) in the worst case for storing edge frequencies.

Ready to solve this problem?

Practice Brick Wall with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Ways to Build Sturdy Brick Wall