554. Brick Wall

MediumArrayHash Table

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 to width.
- For the current width, increment the count in cnt. This width acts as a key and represents the position where a vertical line would cross the edge between adjacent bricks.
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 in cnt using max(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 Evaluator

Example 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:

wall = [
  [3, 5, 1, 1],
  [2, 3, 3, 2],
  [5, 5],
  [4, 4, 2],
  [1, 3, 3, 3],
  [1, 1, 6, 1, 1]
]

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)
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})
Now we have all the running sums in cnt. We don't have an empty cnt, 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: