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:

1. Initialize maxCount = 0 and count = {} (an empty dictionary).
2. Loop through each row of the wall:
   1. Initialize prefix = 0
   2. Loop through each brick width in the row (except the last one):
      1. Add the width to prefix
      2. If prefix is not already in count, add it to count with value 0
      3. Increment count[prefix] by one
      4. If count[prefix] is more than maxCount, update maxCount with count[prefix]
3. 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.