Brick Wall — Solution in Python, Java & C++
Brick Wall solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
Brick Wall is a medium coding problem on arrays, hash table and counting, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Counting
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A rectangular brick wall is given as wall, where wall[i] lists the widths of the bricks in row i from left to right. Every row has the same total width.
Draw a vertical line from top to bottom. The line crosses a brick unless it falls exactly on that brick's edge. The line may not be drawn along either outer border.
Return the fewest bricks the line must cross.
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
Explanation: A line at offset 4 passes through the edges of four rows, so it crosses only the other two.
Example 2
Input: wall = [[1],[1],[1]]
Output: 3
Explanation: Only the outer borders are edges, and those are not allowed — every line crosses all three bricks.
Example 3
Input: wall = [[2,2],[2,2],[1,3]]
Output: 1
Explanation: A line at offset 2 falls on an edge in the first two rows, so it crosses only the third.
Constraints
1 <= wall.length <= 100001 <= wall[i].length <= 10000Each row sums to the same total width.1 <= brick width <= 2147483647
Hints for Brick Wall
Hint 1
Crossing the fewest bricks is the same as passing through the most edges.
Hint 2
For each row, the interior edges sit at its running prefix sums — excluding the final one, which is the outer border.
Hint 3
Tally those offsets across all rows; the busiest offset wins.
How to solve Brick Wall
Flip the objective. A line at a given offset crosses rows - (number of rows whose edge falls there) bricks, so minimising crossings means maximising shared edges.
Approach
- For every row, walk its bricks accumulating a running width and record each running total except the last, which is the wall's right border.
- Tally these offsets in a hash map across all rows.
- The answer is
wall.length - maxTally.
Why it works
Each row contributes at most one edge at a given offset, so the tally at an offset is exactly the number of rows the line slips through. Excluding the final prefix sum is what enforces the rule against drawing along the outer border — and it also handles the all-one-brick case, where no offsets are recorded and the answer is every row.
Complexity
- Time —
O(total bricks) - Space —
O(distinct offsets)
Pitfalls
- Including the last prefix sum makes the right border look like the best line and returns 0.
- Brick widths reach the 32-bit limit, so the running offset needs 64 bits in fixed-width languages.
- Scanning candidate offsets one by one is hopeless — the wall can be billions of units wide.
Reference solution
Python
from typing import List
def leastBricks(wall: List[List[int]]) -> int:
edges = {}
best = 0
for row in wall:
x = 0
for w in row[:-1]:
x += w
edges[x] = edges.get(x, 0) + 1
best = max(best, edges[x])
return len(wall) - bestJava
public static int leastBricks(int[][] wall) {
Map<Long, Integer> edges = new HashMap<>();
int best = 0;
for (int[] row : wall) {
long x = 0;
for (int i = 0; i + 1 < row.length; i++) {
x += row[i];
int c = edges.getOrDefault(x, 0) + 1;
edges.put(x, c);
if (c > best) best = c;
}
}
return wall.length - best;
}C++
int leastBricks(vector<vector<int>>& wall) {
unordered_map<long long, int> edges;
int best = 0;
for (auto& row : wall) {
long long x = 0;
for (size_t i = 0; i + 1 < row.size(); i++) {
x += row[i];
int c = ++edges[x];
if (c > best) best = c;
}
}
return (int) wall.size() - best;
}JavaScript
var leastBricks = function(wall) {
var edges = {}, best = 0;
for (var r = 0; r < wall.length; r++) {
var row = wall[r], x = 0;
for (var i = 0; i + 1 < row.length; i++) {
x += row[i];
var key = String(x);
edges[key] = (edges[key] === undefined ? 0 : edges[key]) + 1;
if (edges[key] > best) best = edges[key];
}
}
return wall.length - best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets