554. Brick Wall LeetCode Solution

In this guide, you will get 554. Brick Wall LeetCode Solution with the best time and space complexity. The solution to Brick Wall problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Brick Wall solution in C++
Brick Wall solution in Java
Brick Wall solution in Python
Additional Resources

Problem Statement of Brick Wall

There is a rectangular brick wall in front of you with n rows of bricks. The ith row has some number of bricks each of the same height (i.e., one unit) but they can be of different widths. The total width of each row is the same.
Draw a vertical line from the top to the bottom and cross the least bricks. If your line goes through the edge of a brick, then the brick is not considered as crossed. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.
Given the 2D array wall that contains the information about the wall, return the minimum number of crossed bricks after drawing such a vertical line.

Example 1:

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2

Example 2:

Input: wall = [[1],[1],[1]]
Output: 3

Constraints:

n == wall.length
1 <= n <= 104
1 <= wall[i].length <= 104
1 <= sum(wall[i].length) <= 2 * 104
sum(wall[i]) is the same for each row i.
1 <= wall[i][j] <= 231 – 1

Complexity Analysis

Time Complexity: O(n), where n = |\text{bricks}|
Space Complexity:

554. Brick Wall LeetCode Solution in C++

class Solution {
 public:
  int leastBricks(vector<vector<int>>& wall) {
    int maxCount = 0;
    unordered_map<int, int> count;

    for (const vector<int>& row : wall) {
      int prefix = 0;
      for (int i = 0; i < row.size() - 1; ++i) {
        prefix += row[i];
        maxCount = max(maxCount, ++count[prefix]);
      }
    }

    return wall.size() - maxCount;
  }
};
/* code provided by PROGIEZ */

554. Brick Wall LeetCode Solution in Java

class Solution {
  public int leastBricks(List<List<Integer>> wall) {
    int maxFreq = 0;
    Map<Integer, Integer> count = new HashMap<>();

    for (List<Integer> row : wall) {
      int prefix = 0;
      for (int i = 0; i < row.size() - 1; ++i) {
        prefix += row.get(i);
        maxFreq = Math.max(maxFreq, count.merge(prefix, 1, Integer::sum));
      }
    }

    return wall.size() - maxFreq;
  }
}
// code provided by PROGIEZ

554. Brick Wall LeetCode Solution in Python

class Solution:
  def leastBricks(self, wall: list[list[int]]) -> int:
    maxFreq = 0
    count = collections.defaultdict(int)

    for row in wall:
      prefix = 0
      for i in range(len(row) - 1):
        prefix += row[i]
        count[prefix] += 1
        maxFreq = max(maxFreq, count[prefix])

    return len(wall) - maxFreq
 # code by PROGIEZ