Last updated on January 12th, 2025 at 03:49 am
Here, we see a Brick Wall LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Hash Table
Companies
Level of Question
Medium
Brick Wall LeetCode Solution
Table of Contents
1. Problem Statement
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
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Prefix Sum with Hash Map”. This pattern involves calculating cumulative sums (prefix sums) and using a hash map to track the frequency of these sums. The goal is to identify the most common edge positions (excluding the last edge of each row) where bricks align, minimizing the number of bricks crossed by a vertical line.
3. Code Implementation in Different Languages
3.1 Brick Wall C++
class Solution {
public:
int leastBricks(vector<vector<int>>& wall) {
unordered_map<int, int> edge_frequency;
int max_frequency = 0;
for(int row=0; row<wall.size(); row++)
{
int edge_postion = 0;
for(int brick_no=0; brick_no< wall[row].size() -1; brick_no++)
{
int current_brick_length = wall[row][brick_no];
edge_postion = edge_postion + current_brick_length ;
edge_frequency[edge_postion]++;
max_frequency = max(edge_frequency[edge_postion],max_frequency);
}
}
return wall.size() - max_frequency;
}
};
3.2 Brick Wall Java
class Solution {
public int leastBricks(List<List<Integer>> wall) {
var edge_frequency=new HashMap<Integer,Integer>();
int max_frequency = 0;
for(int row=0; row<wall.size(); row++)
{
int edge_postion = 0;
for(int brick_no=0; brick_no< wall.get(row).size() -1; brick_no++)
{
int current_brick_length = wall.get(row).get(brick_no);
edge_postion = edge_postion + current_brick_length ;
edge_frequency.put(edge_postion,edge_frequency.getOrDefault(edge_postion,0)+1);
max_frequency = Math.max(edge_frequency.get(edge_postion),max_frequency);
}
}
return wall.size() - max_frequency;
}
}
3.3 Brick Wall JavaScript
var leastBricks = function(wall) {
let freq = new Map(), best = 0
for (let i = 0; i < wall.length; i++) {
let row = wall[i], rowSum = row[0]
for (let j = 1; j < row.length; j++) {
freq.set(rowSum, (freq.get(rowSum) || 0) + 1)
rowSum += row[j]
}
}
for (let [k,v] of freq)
if (v > best) best = v
return wall.length - best
};
3.4 Brick Wall Python
class Solution(object):
def leastBricks(self, wall):
d = collections.defaultdict(int)
for line in wall:
i = 0
for brick in line[:-1]:
i += brick
d[i] += 1
# print len(wall), d
return len(wall)-max(d.values()+[0])
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n * m) | O(n * m) |
| Java | O(n * m) | O(n * m) |
| JavaScript | O(n * m) | O(n * m) |
| Python | O(n * m) | O(n * m) |
- The code uses a Prefix Sum with Hash Map pattern to solve the problem efficiently.
- The time complexity is proportional to the total number of bricks in the wall (
n * m). - The space complexity depends on the number of unique edge positions, which can be at most
n * min the worst case.