Brick Wall
Medium HashMap of edge positions
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A wall is made of rows of bricks of different widths (all rows equally wide). Draw one vertical line top to bottom crossing the fewest bricks; lines along brick edges don't cross them. Return the minimum crossed.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: where should a vertical line go to cross the fewest bricks?
Why this works: crossing fewest bricks = passing through the most brick edges. Count the edge positions across rows.
Example: rows [1,2,2,1], [3,1,2], [1,3,2] …
edge at position 4 appears in most rowsanswer = rows - that count
✦Hints open one at a time
↗Approach
Count edge positions across all rows in a HashMap. The answer is rows − (largest count).
</>Solution (Java)
import java.util.*;
class Solution {
public int leastBricks(List<List<Integer>> wall) {
Map<Integer, Integer> edges = new HashMap<>();
int most = 0;
for (List<Integer> row : wall) {
int pos = 0;
for (int i = 0; i < row.size() - 1; i++) { // skip the last brick's right edge
pos += row.get(i);
most = Math.max(most, edges.merge(pos, 1, Integer::sum));
}
}
return wall.size() - most;
}
}!Common mistake
Including the right edge of the wall, which every row shares — it's not allowed.
- Time: O(total bricks).
- Space: O(number of distinct edges).