554. Brick Wall
Problem Description
There's a wall constructed of multiple rows of bricks of varying widths, but each row has the same total width. Think of this like having a bunch of different sized blocks and trying to stack them up so that they all align perfectly at the ends of the wall, but between the ends, the sizes could mismatch. The goal here is to draw a vertical line from the top of the wall to the bottom, going through as few bricks as possible. Here’s the catch – you can't draw the line at the very edges since that would technically cross no bricks and defeats the purpose of the question. Moreover, if the line goes through the joint between two bricks, it doesn't count as crossing a brick. You are given a 2D array wall
, which represents the layout of the wall where each inner array contains the widths of the bricks in that row.
To solve this problem, you must determine the position where the line crosses the minimum number of bricks and return that number. Imagine this like trying to find the weakest point in the wall where if you had to punch through it (without hitting the edges), you'd break the least amount of bricks.
Intuition
The solution comes down to finding the place in the wall with the most edges of bricks aligned vertically (not including the far left and far right of the wall). If you think about it, the more brick edges you have aligned in a vertical line, the fewer bricks your vertical line will cross.
What we do in the solution is essentially a counting exercise. For every row in the wall, we add up the widths of bricks and note down the running total (except the last brick because it touches the edge of the wall). Each running total represents a position where a vertical line crosses an edge between bricks, thus not crossing a brick itself. So we use a count map, a hash table, where keys are these totals (positions on the wall) and values are how many times we’ve seen this position across different rows. For every position (total width from the start of the wall), we increase the corresponding count.
Finally, we figure out the position with the highest count – the one that occurred most frequently across all rows, meaning our line would cross the least bricks at this position. We then subtract this maximum count from the total number of rows, giving us the least number of bricks our vertical line would cross.
The Python code provided uses this approach efficiently. It iterates through each row, computes the running totals, updates counts, and in the end, finds the maximum value in the counts map, which represents the most common edge alignment across the wall. Subtracting this from the total number of rows yields the minimum number of bricks the line crosses.
Solution Approach
The key idea is to utilize a hash table to maintain the frequency of particular positions where a vertical line can cross through brick edges rather than the bricks themselves. We iterate over each row of the wall, and within each row, iterate over the width of each brick up until the second to last brick. We exclude the last brick because the edge of the last brick aligns with the edge of the wall, and the rules state we cannot draw a line there.
Here is a step-by-step breakdown of the algorithm:
-
Initialize an empty hash table
cnt
to store the frequencies of the crossed edges' positions. -
Iterate over each row in
wall
. For each row:- Initialize a running sum
width
which will keep track of the position as we add up the widths of the bricks. - Go through each brick in the row except the last one (
row[:-1]
), adding the width of the brick towidth
. - For the current
width
, increment the count incnt
. Thiswidth
acts as a key and represents the position where a vertical line would cross the edge between adjacent bricks.
- Initialize a running sum
-
After processing all rows, check if
cnt
is empty. If it is, that means every row is just one brick, so any vertical line will cross all the bricks. Therefore, return the number of rows as the number of crossed bricks. -
If
cnt
is not empty, find the maximum frequency stored incnt
usingmax(cnt, key=cnt.get)
. This represents the edge position that has been encountered the most and where the line will cross the least number of bricks. -
The minimum number of crossed bricks would be the total number of rows minus the maximum frequency edge, calculated as
len(wall) - cnt[max(cnt, key=cnt.get)]
.
In this approach, the time complexity arises from iterating over all bricks once, giving O(n) complexity, where n is the total number of bricks. The space complexity is O(m), where m is the width of the wall as this dictates the maximum number of potential positions for the edges, hence the number of keys in the hash table.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us consider a wall represented by the following 2D array, where each inner array contains the widths of the bricks in a particular row:
1wall = [ 2 [3, 5, 1, 1], 3 [2, 3, 3, 2], 4 [5, 5], 5 [4, 4, 2], 6 [1, 3, 3, 3], 7 [1, 1, 6, 1, 1] 8]
Step-by-step walkthrough:
-
We begin by initializing a hash table
cnt
that will count the frequency of crossed edges' positions (excluding the end edges of the wall).cnt
looks like{}
. -
As we iterate through the wall row by row, we will keep a running sum of the brick widths for each row, stopping before the last brick.
-
For the first row
[3, 5, 1, 1]
, the running sums of widths are:- After first brick: 3 (
cnt
now looks like{3: 1}
) - After second brick: 3+5=8 (
cnt
now looks like{3: 1, 8: 1}
) - After third brick: 8+1=9 (we don't count the last brick edge)
- After first brick: 3 (
-
We repeat this for each subsequent row:
- Second row
[2, 3, 3, 2]
gives us edges at: 2, and 5 (cnt
becomes{3: 1, 8: 1, 2: 1, 5: 1}
) - Third row
[5, 5]
has only one internal edge at: 5 (cnt
becomes{3: 1, 8: 1, 2: 1, 5: 2}
) - Fourth row
[4, 4, 2]
contributes edges at: 4, and 8 (cnt
becomes{3: 1, 8: 2, 2: 1, 5: 2, 4: 1}
) - Fifth row
[1, 3, 3, 3]
adds edges at: 1, 4, and 7 (cnt
becomes{3: 1, 8: 2, 2: 1, 5: 2, 4: 2, 1: 1, 7: 1}
) - Last row
[1, 1, 6, 1, 1]
has edges at: 1, 2, and 8 (cnt
becomes{3: 1, 8: 3, 2: 2, 5: 2, 4: 2, 1: 2, 7: 1}
)
- Second row
-
Now we have all the running sums in
cnt
. We don't have an emptycnt
, meaning we have valid edge positions to consider. -
We find the maximum frequency in
cnt
, which is 3 at position 8. -
Finally, we calculate the minimum number of crossed bricks as the total number of rows
len(wall)
which is 6, minus the maximum frequency encountered, which is 3. -
Therefore, drawing a vertical line at the position that corresponds to the total width of 8 (from the left) would cross the minimum number of bricks, which is
6 - 3 = 3
.
In this example, the least number of bricks that would be crossed by drawing a vertical line anywhere in the wall is 3.
Solution Implementation
1from collections import defaultdict
2
3class Solution:
4 def leastBricks(self, wall: List[List[int]]) -> int:
5 # Create a dictionary to count the frequency of each edge's position (except for the last edge of each row)
6 edge_count = defaultdict(int)
7
8 # Iterate over each row in the wall
9 for row in wall:
10 width = 0 # Initialize width to track the current position of edges
11
12 # Iterate over each brick in the row, except the last brick
13 for brick in row[:-1]:
14 width += brick # Increase the width by the current brick's length to find the next edge
15 edge_count[width] += 1 # Increment the count of the edge at the corresponding width
16
17 # If there are no edges counted, return the number of rows (since a vertical line would cross all rows)
18 if not edge_count:
19 return len(wall)
20
21 # Find the maximum occurrence of a common edge and subtract it from the total rows.
22 # This gives the minimum number of rows crossed by a vertical line.
23 return len(wall) - max(edge_count.values())
24
1// Solution to find the path through a brick wall that crosses the least number of bricks.
2class Solution {
3
4 // Function to determine the minimum number of bricks that must be crossed.
5 // wall: List of lists representing the wall where each list is a row of bricks.
6 public int leastBricks(List<List<Integer>> wall) {
7
8 // A map to store the frequency of edges lining up vertically at each width index.
9 Map<Integer, Integer> edgeFrequency = new HashMap<>();
10
11 // Iterate over each row in the wall.
12 for (List<Integer> row : wall) {
13 int width = 0; // Tracks the cumulative width of bricks as we go along the row.
14
15 // Iterate over the row, skipping the last brick to prevent counting the edge of the wall.
16 for (int i = 0, n = row.size() - 1; i < n; i++) {
17 width += row.get(i); // Add the width of the current brick to the total width.
18
19 // Increase the count of the occurrence of this edge in the map.
20 edgeFrequency.merge(width, 1, Integer::sum);
21 }
22 }
23
24 // Find the maximum frequency of an edge lining up.
25 // If no edges line up, the default maximum will be 0.
26 int maxFrequency = edgeFrequency.values().stream().max(Comparator.naturalOrder()).orElse(0);
27
28 // The minimum number of bricks crossed is the total number of rows minus the max frequency of an edge.
29 return wall.size() - maxFrequency;
30 }
31}
32
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5/**
6 * Function to find the minimum number of bricks that must be cut to create a vertical line that goes through the entire wall.
7 * @param wall - 2D vector where each sub-vector represents a row of bricks in the wall
8 * @return The minimum number of bricks that must be cut
9 */
10int leastBricks(const std::vector<std::vector<int>>& wall) {
11 // Create a hash map to keep track of how many edges align at each width index
12 std::unordered_map<int, int> edge_count;
13
14 // Loop over each row of the wall
15 for (const auto& row : wall) {
16 int cumulative_width = 0; // Tracks the cumulative width as we add bricks
17
18 // Iterate over the row up to the second to last brick to avoid considering the edge of the wall
19 for (size_t i = 0; i < row.size() - 1; ++i) {
20 cumulative_width += row[i]; // Add the width of the current brick to the cumulative width
21
22 // Increment the edge count for the current cumulative width, defaulting to 0 for the first time
23 edge_count[cumulative_width]++;
24 }
25 }
26
27 // Find the maximum count of aligned edges (excluding the wall's edges)
28 int max_aligned_edges = 0;
29 for (const auto& count : edge_count) {
30 max_aligned_edges = std::max(max_aligned_edges, count.second);
31 }
32
33 // The minimum cuts needed is the total number of rows minus the maximum number of aligned edges
34 return wall.size() - max_aligned_edges;
35}
36
37// Usage example:
38int main() {
39 std::vector<std::vector<int>> example_wall = {
40 {1, 2, 2, 1},
41 {3, 1, 2},
42 {1, 3, 2},
43 {2, 4},
44 {3, 1, 2},
45 {1, 3, 1, 1}
46 };
47
48 int cuts_needed = leastBricks(example_wall);
49 std::cout << cuts_needed << std::endl; // Output will be the result of calling leastBricks on example_wall
50
51 return 0;
52}
53
1/**
2 * Function to find the minimum number of bricks that must be cut to create a vertical line that goes through the entire wall.
3 * @param {number[][]} wall - 2D array where each sub-array represents a row of bricks in the wall
4 * @return {number} - The minimum number of bricks that must be cut
5 */
6const leastBricks = (wall: number[][]): number => {
7 // Create a map to keep track of how many edges align at each width index
8 const edgeCount: Map<number, number> = new Map();
9
10 // Loop over each row of the wall
11 for (const row of wall) {
12 let cumulativeWidth: number = 0; // Tracks the cumulative width as we add bricks
13
14 // Iterate over the row up to the second to last brick to avoid considering the edge of the wall
15 for (let i = 0; i < row.length - 1; i++) {
16 cumulativeWidth += row[i]; // Add the width of the current brick to the cumulative width
17
18 // Increment the edge count for the current cumulative width, defaulting to 0 for the first time
19 edgeCount.set(cumulativeWidth, (edgeCount.get(cumulativeWidth) || 0) + 1);
20 }
21 }
22
23 // Find the maximum count of aligned edges (excluding the wall's edges)
24 let maxAlignedEdges: number = 0;
25 for (const count of edgeCount.values()) {
26 maxAlignedEdges = Math.max(maxAlignedEdges, count);
27 }
28
29 // The minimum cuts needed is the total number of rows minus the maximum number of aligned edges
30 return wall.length - maxAlignedEdges;
31};
32
33// Usage example (should be removed from the final code as it's not part of the requested rewrite):
34const exampleWall: number[][] = [
35 [1, 2, 2, 1],
36 [3, 1, 2],
37 [1, 3, 2],
38 [2, 4],
39 [3, 1, 2],
40 [1, 3, 1, 1]
41];
42const cutsNeeded: number = leastBricks(exampleWall);
43console.log(cutsNeeded); // Output would be the result of calling leastBricks on exampleWall
44
Time and Space Complexity
Time Complexity
The time complexity of the code is mainly determined by the two nested loops. The outer loop iterates through each row in the wall, which is O(n)
where n
is the number of rows. The inner loop iterates through each brick in the row, excluding the last brick. The total number of bricks in all rows is equivalent to the total number of iterations of the inner loop. Let's denote m
as the average number of bricks per row. Therefore, the total complexity would approximately be O(n * m)
.
However, in the worst-case scenario, m
(the number of bricks per row) could be proportional to the width of the wall if the bricks are very narrow. If w
represents the wall's width, then the complexity could also be expressed as O(n * w)
in such a case.
Finally, the complexity also includes the time required to find the max
in the defaultdict cnt
, which, in the worst case, is O(w)
, where w
is the unique widths that are less than the wall's width. This is because, in the worst case, each possible width could have a different number of edges crossing it.
So, the overall time complexity is O(n * m)
or O(n * w) + O(w)
, which simplifies to O(n * w)
because we drop the less significant term.
Space Complexity
The space complexity is influenced by the defaultdict cnt
, which stores the frequency of edge crossings at each width position. In the worst case, every possible position could have an edge crossing, so the space complexity would be O(w)
where w
is the unique widths less than the wall's width. Therefore, the space complexity is O(w)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.