Leetcode 554. Brick Wall
Problem Explanation
We are given a wall composed of rows of bricks of varied lengths but the same height. We need to draw a vertical line from top to bottom, which crosses the least number of bricks. The wall composition is given as a list of lists, wherein each list are the widths of bricks from left to right in each row.
If our line falls on the edge of a brick (including where two bricks meet), we do not consider it as crossing a brick. We can't draw the line along one of the vertical edges of the wall where obviously, no brick will be crossed. We need to design an algorithm to find out the minimum number of crossed bricks and return this minimum number.
Walk-through Example
Consider the following input:
1wall = [[1,2,2,1], 2 [3,1,2], 3 [1,3,2], 4 [2,4], 5 [3,1,2], 6 [1,3,1,1]]
There are six rows of bricks. In this wall, if we draw a line anywhere between the 1st and 2nd brick of the 1st row it will cross 2 bricks, which is the minimum number of crossed bricks. Hence the function returns 2.
Algorithm Explanation
This problem can be solved by using a hash table (unordered_map in C++ or dictionary in python). The approach is to count the prefixes of the sum of widths of bricks in each row (except the last brick), and store it in the hash table. For every prefix, we increment its count by one, and for every increment, we keep track of which prefix has the maximum count. We then subtract this maximum count from the total number of rows to find the minimum number of bricks crossed.
This approach works because counting the sum of prefixes allows us to find the positions where a brick ends, and incrementing this count allows us to track how many bricks end at that position (or how many edges are there). The maximum count shows us the maximum number of brick-edges we can draw a line through, and since a line must cross either brick or edge in each row, subtracting this maximum count from the total number of rows gives us the minimum number of bricks we must cross.
Algorithm Steps
Using the same example above:
- Initialize maxCount = 0 and count = {} (an empty dictionary).
- Loop through each row of the wall:
- Initialize prefix = 0
- Loop through each brick width in the row (except the last one):
- Add the width to prefix
- If prefix is not already in count, add it to count with value 0
- Increment count[prefix] by one
- If count[prefix] is more than maxCount, update maxCount with count[prefix]
- Return wall.size() - maxCount
Python Solution
1 2python 3from typing import List 4from collections import defaultdict 5 6class Solution: 7 def leastBricks(self, wall: List[List[int]]) -> int: 8 brick_ends = defaultdict(int) 9 max_brick_ends = 0 10 for row in wall: 11 length = 0 12 for brick in row[:-1]: # Ignore the last brick 13 length += brick 14 brick_ends[length] += 1 15 max_brick_ends = max(max_brick_ends, brick_ends[length]) 16 return len(wall) - max_brick_ends
Java Solution
1
2java
3import java.util.*;
4class Solution {
5 public int leastBricks(List<List<Integer>> wall) {
6 Map<Integer, Integer> count = new HashMap<>();
7 int maxCount = 0;
8 for (List<Integer> row : wall) {
9 int prefix = 0;
10 for (int i = 0; i < row.size() - 1; ++i) {
11 prefix += row.get(i);
12 count.put(prefix, count.getOrDefault(prefix, 0) + 1);
13 maxCount = Math.max(maxCount, count.get(prefix));
14 }
15 }
16 return wall.size() - maxCount;
17 }
18}
JavaScript Solution
1 2javascript 3var leastBricks = function(wall) { 4 let maxCount = 0; 5 let count = {}; 6 for(let row of wall) { 7 let prefix = 0; 8 for(let i = 0; i < row.length - 1; i++) { // Ignore the last brick 9 prefix += row[i]; 10 count[prefix] = (count[prefix] || 0) + 1; 11 maxCount = Math.max(maxCount, count[prefix]); 12 } 13 } 14 return wall.length - maxCount; 15};
C++ Solution
1
2cpp
3#include <vector>
4#include <unordered_map>
5using namespace std;
6
7class Solution {
8public:
9 int leastBricks(vector<vector<int>>& wall) {
10 int maxCount = 0;
11 unordered_map<int, int> count;
12 for (const vector<int>& row : wall) {
13 int prefix = 0;
14 for (int i = 0; i < row.size() - 1; ++i) { // Ignore the last brick
15 prefix += row[i];
16 maxCount = max(maxCount, ++count[prefix]);
17 }
18 }
19 return wall.size() - maxCount;
20 }
21};
C# Solution
1 2csharp 3using System; 4using System.Collections.Generic; 5 6public class Solution { 7 public int LeastBricks(IList<IList<int>> wall) { 8 int maxCount = 0; 9 var count = new Dictionary<int, int>(); 10 foreach(var row in wall) { 11 int prefix = 0; 12 for(int i = 0; i < row.Count - 1; i++) { // Ignore the last brick 13 prefix += row[i]; 14 if (!count.ContainsKey(prefix)) count[prefix] = 0; 15 count[prefix]++; 16 maxCount = Math.Max(maxCount, count[prefix]); 17 } 18 } 19 return wall.Count - maxCount; 20 } 21}
Code Explanation
Python
In Python, we initialize a defaultdict brick_ends
to store the sum of bricks and its count. We also initialize max_brick_ends
to 0, which will keep track of the maximum count of brick endings. For each row in the wall, and for each brick in row (excluding the last brick), we add the width of the brick to length
. Then, we increment the count of that length
in brick_ends
and update max_brick_ends
if necessary. In the end, we return the length of the wall minus max_brick_ends
.
Java
The Java solution is very similar to the Python solution. Here, we handle the brick_ends
dictionary manually by checking if prefix
(representing length
in Python) is present in our dictionary or not. For each row and each brick, we calculate the prefix
and update our count
map. If we have more counts of a prefix than maxCount
, we update maxCount
. In the end, we return the size of the wall minus maxCount
.
JavaScript
The JavaScript solution follows the same logic as the previous ones. Here, using JavaScriptโs map object, we increment the count for each width of the brick. JavaScriptโs Math.max
function is used to find the maximum of counts.
C++
In C++, we start by declaring two variables count
and maxCount
. Here count
is an unordered map which will store the sum of bricks and its count. For each row in the wall, and for each brick in row (excluding the last one), we calculate the prefix
by adding the width of bricks. Then, we calculate the maxCount
using the max
function. Finally, we return the total row count minus maxCount
.
C#
This implementation is quite similar to the Java solution, but in C#. For each row and for each brick, we calculate the prefix
(sum of brick widths) and update count
accordingly. maxCount
keeps track of the maximum count in the count
map. At last, we return the difference of wallโs count and maxCount
.
Complexity analysis
Time complexity of the solution is O(N), as we are looping over the given wall list only once. Here, N is the number of total bricks in the wall.
The space complexity is also O(N), because in the worst case scenario, we might end up storing each brick in our count map in case all bricks have different widths.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.