554. Brick Wall

Problem Description

Given a rectangular brick wall represented as a 2D array wall, where each inner array represents a row of bricks and the integers represent the width of each brick, find the minimum number of bricks crossed by a vertical line drawn from top to bottom that doesn't go through the edge of any brick.

Solution: Hash Table and Prefix Sums

The optimal solution utilizes a hash table (or dictionary) to store the prefix sums of brick widths in each row. The key idea is that if a vertical line passes through a point corresponding to a frequently occurring prefix sum, it will cross fewer bricks.

Algorithm:

1. Calculate Prefix Sums: Iterate through each row of the wall. For each row, calculate the cumulative sum of brick widths up to (but not including) the last brick. Store these prefix sums in a hash table, using the prefix sum as the key and the count of its occurrences as the value.

2. Find the Most Frequent Prefix Sum: After processing all rows, find the prefix sum that appears most frequently in the hash table. This represents the position where a vertical line would intersect the fewest bricks.

3. Calculate Minimum Crossings: The minimum number of crossed bricks is the total number of rows minus the maximum count found in step 2.

Time Complexity: O(M * N), where M is the number of rows and N is the maximum number of bricks in a row. This is because we iterate through each brick once.

Space Complexity: O(M * N) in the worst case, although it's typically much less. The hash table's size depends on the unique prefix sums encountered, which could be up to M * N in a pathological case but is usually significantly smaller.

Code Implementation (Python)

from collections import Counter
 
class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        prefix_sums = Counter()
        for row in wall:
            current_sum = 0
            for i in range(len(row) - 1):  # Exclude the last brick
                current_sum += row[i]
                prefix_sums[current_sum] += 1
 
        # Find the most frequent prefix sum (maximum count)
        max_count = max(prefix_sums.values()) if prefix_sums else 0
        return len(wall) - max_count
 

Code Implementation (Java)

import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> prefixSums = new HashMap<>();
        for (List<Integer> row : wall) {
            int currentSum = 0;
            for (int i = 0; i < row.size() - 1; i++) { // Exclude the last brick
                currentSum += row.get(i);
                prefixSums.put(currentSum, prefixSums.getOrDefault(currentSum, 0) + 1);
            }
        }
 
        int maxCount = 0;
        for (int count : prefixSums.values()) {
            maxCount = Math.max(maxCount, count);
        }
        return wall.size() - maxCount;
    }
}

Code Implementation (C++)

#include <vector>
#include <unordered_map>
#include <algorithm>
 
using namespace std;
 
class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> prefixSums;
        for (const auto& row : wall) {
            int currentSum = 0;
            for (size_t i = 0; i < row.size() - 1; ++i) { // Exclude last brick
                currentSum += row[i];
                prefixSums[currentSum]++;
            }
        }
 
        int maxCount = 0;
        for (const auto& pair : prefixSums) {
            maxCount = max(maxCount, pair.second);
        }
        return wall.size() - maxCount;
    }
};

Note: The other language implementations (JavaScript, TypeScript, Go) follow a very similar structure, adapting the specific syntax and data structures of each language. The core algorithm remains the same.