Brick Wall solution and explanation
Google
9 more videos on this problem
Brick Wall - Leetcode 554 - PythonNeetCode · 14:40 · 28K views
Leetcode #554. Brick Wall || Code +Explanation + Example WalkthroughCode with Alisha · 11:49 · 3K views
Brick Wall | Live Coding with Explanation | Leetcode - 554Algorithms Made Easy · 9:33 · 2K views
LeetCode - 554. Brick Wall | Day 22 April ChallengeAditya Mahajan · 10:49 · 1K views
Leetcode - Brick Wall (Python)Timothy H Chang · 6:27 · 701 views
Brick Wall | LeetCode 554 | Coders CampCoders Camp · 9:49 · 359 views
Brick Wall | Binary Search | O(nlogn) | 554 LeetCode | LeetCode Explore | Day 22CodeWithSunny · 23:34 · 357 views
Brick Wall - LeetCode 554 - PythonAlpha-Code · 11:11 · 354 views
LeetCode 554. Brick WallHappy Coding · 14:44 · 264 views
Daily Leetcode #387 part 2: Apr 22, 2021 - 554. Brick WallProgramming Live with Larry · 9:06 · 239 views
The 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.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
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.
from collections import defaultdict
def least_bricks(wall):
edge_count = defaultdict(int)
for row in wall:
prefix_sum = 0
for brick in row[:-1]: # Exclude the last edge in each row
prefix_sum += brick
edge_count[prefix_sum] += 1
if not edge_count:
return len(wall)
max_edges = max(edge_count.values())
return len(wall) - max_edgesThe 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.
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.
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.
import java.util.*;
public class BrickWall {
public int leastBricks(List<List<Integer>> wall) {
Map<Integer, Integer> edgeCount = new HashMap<>();
for (List<Integer> row : wall) {
int prefixSum = 0;
for (int j = 0; j < row.size() - 1; j++) {
prefixSum += row.get(j);
edgeCount.put(prefixSum, edgeCount.getOrDefault(prefixSum, 0) + 1);
}
}
int maxEdges = 0;
for (int count : edgeCount.values()) {
maxEdges = Math.max(maxEdges, count);
}
return wall.size() - maxEdges;
}
}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.
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.
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.
def minCrossedBricks(wall):
from collections import defaultdict
edge_count = defaultdict(int)
max_edges = 0
for row in wall:
prefix_sum = 0
for brick in row[:-1]:
prefix_sum += brick
edge_count[prefix_sum] += 1
max_edges = max(max_edges, edge_count[prefix_sum])
return len(wall) - max_edges
wall = [[1, 2, 2, 1], [3, 1, 2], [1, 3, 2], [2, 4], [3, 1, 2], [1, 3, 1, 1]]
print("Minimum crossed bricks:", minCrossedBricks(wall))import java.util.HashMap;
import java.util.List;
public class Solution {
public int minCrossedBricks(List<List<Integer>> wall) {
HashMap<Integer, Integer> edge_count = new HashMap<>();
int max_edges = 0;
for (List<Integer> row : wall) {
int prefix_sum = 0;
for (int i = 0; i < row.size() - 1; i++) {
prefix_sum += row.get(i);
edge_count.put(prefix_sum, edge_count.getOrDefault(prefix_sum, 0) + 1);
max_edges = Math.max(max_edges, edge_count.get(prefix_sum));
}
}
return wall.size() - max_edges;
}
public static void main(String[] args) {
List<List<Integer>> wall = List.of(
List.of(1, 2, 2, 1),
List.of(3, 1, 2),
List.of(1, 3, 2),
List.of(2, 4),
List.of(3, 1, 2),
List.of(1, 3, 1, 1)
);
Solution solution = new Solution();
System.out.println("Minimum crossed bricks: " + solution.minCrossedBricks(wall));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int minCrossedBricks(vector<vector<int>>& wall) {
unordered_map<int, int> edge_count;
int max_edges = 0;
for (const auto& row : wall) {
int prefix_sum = 0;
for (int j = 0; j < row.size() - 1; ++j) {
prefix_sum += row[j];
edge_count[prefix_sum]++;
max_edges = max(max_edges, edge_count[prefix_sum]);
}
}
return wall.size() - max_edges;
}
int main() {
vector<vector<int>> wall = {
{1, 2, 2, 1},
{3, 1, 2},
{1, 3, 2},
{2, 4},
{3, 1, 2},
{1, 3, 1, 1}
};
cout << "Minimum crossed bricks: " << minCrossedBricks(wall) << endl;
return 0;
}function minCrossedBricks(wall) {
const edge_count = new Map();
let max_edges = 0;
for (const row of wall) {
let prefix_sum = 0;
for (let i = 0; i < row.length - 1; i++) {
prefix_sum += row[i];
if (!edge_count.has(prefix_sum)) {
edge_count.set(prefix_sum, 0);
}
edge_count.set(prefix_sum, edge_count.get(prefix_sum) + 1);
max_edges = Math.max(max_edges, edge_count.get(prefix_sum));
}
}
return wall.length - max_edges;
}
const wall = [
[1, 2, 2, 1],
[3, 1, 2],
[1, 3, 2],
[2, 4],
[3, 1, 2],
[1, 3, 1, 1]
];
console.log("Minimum crossed bricks:", minCrossedBricks(wall));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_ROWS 10000
#define MAX_COLS 10000
int minCrossedBricks(int** wall, int wallSize, int* wallColSize) {
int edge_count[MAX_ROWS * MAX_COLS] = {0};
int max_edges = 0;
for (int i = 0; i < wallSize; ++i) {
int prefix_sum = 0;
for (int j = 0; j < wallColSize[i] - 1; ++j) {
prefix_sum += wall[i][j];
edge_count[prefix_sum]++;
if (edge_count[prefix_sum] > max_edges) {
max_edges = edge_count[prefix_sum];
}
}
}
return wallSize - max_edges;
}
int main() {
int* wall[] = {
(int[]) {1, 2, 2, 1},
(int[]) {3, 1, 2},
(int[]) {1, 3, 2},
(int[]) {2, 4},
(int[]) {3, 1, 2},
(int[]) {1, 3, 1, 1}
};
int wallColSize[] = {4, 3, 3, 2, 3, 4};
int result = minCrossedBricks(wall, 6, wallColSize);
printf("Minimum crossed bricks: %d\n", result);
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public int MinCrossedBricks(IList<IList<int>> wall) {
Dictionary<int, int> edge_count = new Dictionary<int, int>();
int max_edges = 0;
foreach (var row in wall) {
int prefix_sum = 0;
for (int i = 0; i < row.Count - 1; i++) {
prefix_sum += row[i];
if (!edge_count.ContainsKey(prefix_sum)) {
edge_count[prefix_sum] = 0;
}
edge_count[prefix_sum]++;
max_edges = Math.Max(max_edges, edge_count[prefix_sum]);
}
}
return wall.Count - max_edges;
}
static void Main() {
var wall = new List<IList<int>>() {
new List<int> {1, 2, 2, 1},
new List<int> {3, 1, 2},
new List<int> {1, 3, 2},
new List<int> {2, 4},
new List<int> {3, 1, 2},
new List<int> {1, 3, 1, 1}
};
Solution solution = new Solution();
Console.WriteLine("Minimum crossed bricks: " + solution.MinCrossedBricks(wall));
}
}The Python solution makes use of a default dictionary for tallying prefix sums, which simplifies and expedites the process of finding the optimum vertical position by tracking the highest frequency of edges.
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 use of a defaultdict.
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.
function leastBricks(wall: number[][]): number {
const cnt: Map<number, number> = new Map();
for (const row of wall) {
let s = 0;
for (let i = 0; i + 1 < row.length; ++i) {
s += row[i];
cnt.set(s, (cnt.get(s) || 0) + 1);
}
}
const mx = Math.max(...cnt.values(), 0);
return wall.length - mx;
}func leastBricks(wall [][]int) int {
cnt := map[int]int{}
for _, row := range wall {
s := 0
for _, x := range row[:len(row)-1] {
s += x
cnt[s]++
}
}
mx := 0
for _, x := range cnt {
mx = max(mx, x)
}
return len(wall) - mx
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
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.