Brick Wall Solution In C++/Java/Python/JS
Problem Description
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.
Examples:
Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 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
This problem requires finding the least number of bricks a vertical line would intersect when drawn from top to bottom. The key insight is to track the positions of brick edges across all rows and identify the most common edge position. By placing the line at this position, we minimize the number of bricks crossed, leading to an efficient solution using a hashmap to count edge frequencies.
Brute Force Approach
Intuition
A brute-force way to approach this problem is to check every possible vertical position from 1 to the total wall width. For each position, we need to determine how many bricks the line would intersect if drawn there. Since a valid gap only occurs at the sum of brick widths within a row, we must track these positions carefully to identify potential split points.
To do this, we go row by row and compute where each brick ends, marking those positions as possible gap locations. If a position aligns with gaps in multiple rows, it becomes a strong candidate for minimizing brick intersections. By systematically checking all possible positions, we can determine the one that results in the least number of bricks being crossed.
This brute-force approach follows a straightforward "try all possibilities" strategy, making it easy to understand but inefficient for larger inputs. A more optimized approach would use a hashmap to efficiently track edge positions rather than explicitly checking every possible vertical position, significantly reducing redundant computations.
What is Hashmap?
A hashmap is a data structure that stores key-value pairs for efficient lookups, insertions, and deletions. It uses a hash function to map keys to indices in an array, enabling quick access to values. If multiple keys map to the same index (collision), techniques like chaining or open addressing handle them. Hashmaps provide average O(1) time complexityfor basic operations. They are widely used in caching, frequency counting, and fast data retrieval.
Approach
Step 1: Initialize Variables
- Get the number of rows in the wall (n).
- Compute the total width of the wall using the first row.
- Initialize minBricks to n, which represents the worst case where no gaps align.
Step 2: Iterate Over Possible Vertical Positions
- Loop through positions from 1 to width - 1, considering each as a potential split point.
Step 3: Check Each Row for Gaps
- For each position, iterate through all rows in the wall.
- Maintain a cumulative sum while traversing bricks in a row.
- If the sum reaches the current position exactly, it means we found a valid gap, so stop checking further in that row.
- If the sum exceeds the position, it means no gap exists at that point, so move to the next row.
Step 4: Count Bricks Crossed
- If a row does not have a gap at the current position, increment the bricksCrossed counter.
- Update minBricks with the minimum number of bricks crossed across all positions.
Step 5: Return the Minimum Bricks Crossed
- After checking all possible positions, return minBricks, which represents the least number of bricks a vertical line would cross.
Brick Wall Dry run - BruteForce
Input:
wall = [[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]
Step 1: Compute Total Wall Width
The first row is [1, 2, 2, 1]. Summing up the bricks, we get 1 + 2 + 2 + 1 = 6.
So, the total width of the wall is 6. We will check possible vertical positions from 1 to 5.
Step 2: Iterate Over Possible Vertical Positions
Checking position 1:
- Row 1: Bricks [1,2,2,1] → First brick ends at 1 (gap found)
- Row 2: Bricks [3,1,2] → First brick ends at 3 (no gap)
- Row 3: Bricks [1,3,2] → First brick ends at 1 (gap found)
- Row 4: Bricks [2,4] → First brick ends at 2 (no gap)
- Row 5: Bricks [3,1,2] → First brick ends at 3 (no gap)
- Row 6: Bricks [1,3,1,1] → First brick ends at 1 (gap found)
Total bricks crossed = 3
Checking position 2:
- Row 1: First two bricks [1,2] sum to 3 (no gap)
- Row 2: First brick [3] ends at 3 (no gap)
- Row 3: First two bricks [1,3] sum to 4 (no gap)
- Row 4: First brick [2] ends at 2 (gap found)
- Row 5: First brick [3] ends at 3 (no gap)
- Row 6: First two bricks [1,3] sum to 4 (no gap)
Total bricks crossed = 5
Checking position 3:
- Row 1: First two bricks [1,2] sum to 3 (gap found)
- Row 2: First brick [3] ends at 3 (gap found)
- Row 3: First two bricks [1,3] sum to 4 (no gap)
- Row 4: First brick [2] ends at 2 (no gap)
- Row 5: First brick [3] ends at 3 (gap found)
- Row 6: First two bricks [1,3] sum to 4 (no gap)
Total bricks crossed = 3
Checking position 4:
- Row 1: First three bricks [1,2,2] sum to 5 (no gap)
- Row 2: First two bricks [3,1] sum to 4 (gap found)
- Row 3: First two bricks [1,3] sum to 4 (gap found)
- Row 4: First brick [2] ends at 2 (no gap)
- Row 5: First two bricks [3,1] sum to 4 (gap found)
- Row 6: First two bricks [1,3] sum to 4 (gap found)
Total bricks crossed = 2
Checking position 5:
- Row 1: First three bricks [1,2,2] sum to 5 (gap found)
- Row 2: First three bricks [3,1,2] sum to 6 (no gap)
- Row 3: First three bricks [1,3,2] sum to 6 (no gap)
- Row 4: First brick [2] ends at 2 (no gap)
- Row 5: First three bricks [3,1,2] sum to 6 (no gap)
- Row 6: First three bricks [1,3,1] sum to 5 (gap found)
Total bricks crossed = 4
Step 3: Find the Minimum Bricks Crossed
The best position is at position 4, where only 2 bricks are crossed.
Final output: 2
Brick Wall Code for All Languages - BruteForce
C++
class Solution {
public:
int leastBricks(vector<vector<int>>& wall) {
int n = wall.size(); // Number of rows in the wall
int width = 0; // Total width of the wall
// Compute total wall width using the first row
for (int brick : wall[0]) {
width += brick;
}
int minBricks = n; // Initialize with the maximum possible bricks crossed
// Check every possible vertical position from 1 to width-1
for (int pos = 1; pos < width; pos++) {
int bricksCrossed = 0;
for (const auto& row : wall) {
int sum = 0;
bool gapFound = false;
for (int brick : row) {
sum += brick;
if (sum == pos) { // Found a valid gap
gapFound = true;
break;
}
if (sum > pos) break; // No need to check further
}
if (!gapFound) bricksCrossed++;
}
minBricks = min(minBricks, bricksCrossed);
}
return minBricks;
}
};
Brick Wall code in Java - BruteForce
import java.util.List;
class Solution {
public int leastBricks(List<List<Integer>> wall) {
int n = wall.size(); // Number of rows in the wall
int width = 0; // Total width of the wall
// Compute total wall width using the first row
for (int brick : wall.get(0)) {
width += brick;
}
int minBricks = n; // Initialize with the maximum possible bricks crossed
// Check every possible vertical position from 1 to width-1
for (int pos = 1; pos < width; pos++) {
int bricksCrossed = 0;
for (List<Integer> row : wall) {
int sum = 0;
boolean gapFound = false;
for (int brick : row) {
sum += brick;
if (sum == pos) { // Found a valid gap
gapFound = true;
break;
}
if (sum > pos) break; // No need to check further
}
if (!gapFound) bricksCrossed++;
}
minBricks = Math.min(minBricks, bricksCrossed);
}
return minBricks;
}
}Brick Wall code in Python - BruteForce
class Solution:
def leastBricks(self, wall):
n = len(wall) # Number of rows in the wall
width = sum(wall[0]) # Compute total width of the wall using first row
min_bricks = n # Initialize with the maximum possible bricks crossed
# Check every possible vertical position from 1 to width-1
for pos in range(1, width):
bricks_crossed = 0
for row in wall:
total = 0
gap_found = False
for brick in row:
total += brick
if total == pos: # Found a valid gap
gap_found = True
break
if total > pos:
break # No need to check further
if not gap_found:
bricks_crossed += 1
min_bricks = min(min_bricks, bricks_crossed)
return min_bricks
Brick Wall code in Javascript - BruteForce
class Solution {
leastBricks(wall) {
let n = wall.length; // Number of rows in the wall
let width = wall[0].reduce((a, b) => a + b, 0); // Compute total wall width
let minBricks = n; // Initialize with the maximum possible bricks crossed
// Check every possible vertical position from 1 to width-1
for (let pos = 1; pos < width; pos++) {
let bricksCrossed = 0;
for (let row of wall) {
let sum = 0;
let gapFound = false;
for (let brick of row) {
sum += brick;
if (sum === pos) { // Found a valid gap
gapFound = true;
break;
}
if (sum > pos) break; // No need to check further
}
if (!gapFound) bricksCrossed++;
}
minBricks = Math.min(minBricks, bricksCrossed);
}
return minBricks;
}
}
Time Complexity: O(W * N * M)
- The outer loop iterates over every possible vertical position from 1 to width-1. The width is the sum of the bricks in the first row, denoted as W.
- The inner loop iterates over each row, which is N (number of rows in the wall).
- Inside the inner loop, we traverse the row’s bricks, which on average is M (number of bricks per row).
- In the worst case, every brick must be processed, leading to an overall complexity of O(W * N * M).
Since W = sum(wall[0]) and M ≈ W/N, in the worst case, this simplifies to O(W²) when N is large.
Space Complexity:O(1)
Total Space Complexity:
- We do not store additional data structures, only a few integer variables.
- The input wall is already given and does not contribute to extra space.
- Total Space Complexity: O(1) (constant extra space, ignoring input).
Auxiliary Space Complexity:
- We only use a few integer variables (
width,minBricks,sum,bricksCrossed,gapFound), which require O(1)space. - We do not allocate additional memory except for loop variables.
- Auxiliary Space Complexity: O(1).
Optimal Approach
Intuition
Imagine you have a brick wall made of different rows, where each row consists of bricks placed next to each other. Your goal is to draw a vertical line from the top to the bottom of the wall in such a way that it cuts through the fewest number of bricks. But how do you decide where to draw this line?
A good way to think about this problem is to focus on the gaps between bricks rather than the bricks themselves. If multiple rows have a gap at the same position, then drawing the line there will avoid cutting those bricks. So, the best position for the line is where the most brick edges (gaps) align across rows.
To find this, we go through each row and calculate the positions where bricks end (except for the last brick in a row, since we don’t want to cut the wall at its edges). We use a map (unordered_map) to keep track of how many rows have a brick edge at each position. The position with the highest count is the best place to draw the line, as it avoids the most bricks. Finally, to find the answer, we subtract this maximum count from the total number of rows. This tells us the minimum number of bricks the line must pass through.
By thinking about the problem this way, we shift our focus from breaking bricks to aligning edges. This makes the solution much easier to understand and implement using a simple loop and a hash map.
Approach
Step 1: Initialize Variables
- rows to store the number of rows in the wall.
- maxBrickEdges to track the highest number of brick edges at any position.
- edgesFrequency, a hash map (unordered_map<int, int>) to store the count of brick edges at different positions.
Step 2: Count Brick Edge Positions
- Use idx = 0 to track the current position.
- For each brick in the row (excluding the last one), add its width to idx and update edgesFrequency[idx].
- This keeps a count of how many rows have a brick edge at a specific position.
Step 3: Find the Most Frequent Brick Edge
Loop through edgesFrequency to find the position with the maximum brick edges (maxBrickEdges).
- This position represents the best place to draw a vertical line, as it will pass through the most edges and minimize the number of bricks intersected.
Step 4: Compute the Minimum Bricks to Cut
The answer is rows - maxBrickEdges, as the remaining bricks in the rows will be the ones that get cut by the vertical line.
- If no brick edges exist (i.e., maxBrickEdges remains 0), the worst-case scenario is cutting through all rows.
Brick Wall Dry run - Optimised
Input:
wall = [[1,2,2,1], [3,1,2], [1,3,2], [2,4], [3,1,2], [1,3,1,1]]
Step 1: Initialize Variables
- rows = 6 (since there are 6 rows in the wall).
- maxBrickEdges = 0 (to track the highest number of brick edges at any position).
- edgesFrequency = {} (a hashmap to store edge positions and their counts).
Step 2: Process Each Row to Find Edge Positions
We iterate over each row and track where the brick edges appear.
Row 1: [1, 2, 2, 1]
- Start at idx = 0.
- Add 1 → idx = 1 → edgesFrequency = {1: 1}
- Add 2 → idx = 3 → edgesFrequency = {1: 1, 3: 1}
- Add 2 → idx = 5 → edgesFrequency = {1: 1, 3: 1, 5: 1}
Row 2: [3, 1, 2]
- Start at idx = 0.
- Add 3 → idx = 3 → edgesFrequency = {1: 1, 3: 2, 5: 1}
- Add 1 → idx = 4 → edgesFrequency = {1: 1, 3: 2, 4: 1, 5: 1}
Row 3: [1, 3, 2]
- Start at idx = 0.
- Add 1 → idx = 1 → edgesFrequency = {1: 2, 3: 2, 4: 1, 5: 1}
- Add 3 → idx = 4 → edgesFrequency = {1: 2, 3: 2, 4: 2, 5: 1}
Row 4: [2, 4]
- Start at idx = 0.
- Add 2 → idx = 2 → edgesFrequency = {1: 2, 2: 1, 3: 2, 4: 2, 5: 1}
Row 5: [3, 1, 2]
- Start at idx = 0.
- Add 3 → idx = 3 → edgesFrequency = {1: 2, 2: 1, 3: 3, 4: 2, 5: 1}
- Add 1 → idx = 4 → edgesFrequency = {1: 2, 2: 1, 3: 3, 4: 3, 5: 1}
Row 6: [1, 3, 1, 1]
- Start at idx = 0.
- Add 1 → idx = 1 → edgesFrequency = {1: 3, 2: 1, 3: 3, 4: 3, 5: 1}
- Add 3 → idx = 4 → edgesFrequency = {1: 3, 2: 1, 3: 3, 4: 4, 5: 1}
- Add 1 → idx = 5 → edgesFrequency = {1: 3, 2: 1, 3: 3, 4: 4, 5: 2}
Step 3: Find Maximum Edge Frequency
- The maximum frequency of brick edges is 4, occurring at position 4.
- This means a vertical line at position 4 crosses the fewest bricks.
Step 4: Compute Minimum Bricks to Cut
Formula: rows - maxBrickEdges = 6 - 4 = 2
Thus, the minimum number of bricks the vertical line will cut through is 2.
Final Output:2
Brick Wall Code for All Languages - Optimised
C++
class Solution {
public:
int leastBricks(vector<vector<int>>& wall) {
int rows = wall.size();
// Total number of rows (height of the wall)
int maxBrickEdges = 0;
// Stores the maximum number of brick edges found at any position
unordered_map<int, int> edgesFrequency;
// HashMap to count brick edges at each position
for (auto& row : wall) {
int idx = 0;
// Tracks the current edge position
for (int i = 0; i < row.size() - 1; i++) {
idx += row[i];
// Move to the next edge position
edgesFrequency[idx]++;
// Increment edge count at this position
}
}
for (auto& pair : edgesFrequency) {
maxBrickEdges = max(maxBrickEdges, pair.second);
// Find the maximum count of brick edges at any position
}
return rows - maxBrickEdges;
// The minimum number of bricks that need to be cut
}
};Brick Wall Code in Java - Optimised
import java.util.*;
class Solution {
public int leastBricks(List<List<Integer>> wall) {
int rows = wall.size();
// Total number of rows (height of the wall)
int maxBrickEdges = 0;
// HashMap to count brick edges at each position
Map<Integer, Integer> edgesFrequency = new HashMap<>();
for (List<Integer> row : wall) {
int idx = 0;
// Tracks the current edge position
for (int i = 0; i < row.size() - 1; i++) {
idx += row.get(i);
// Move to the next edge position
edgesFrequency.put(idx, edgesFrequency.getOrDefault(idx, 0) + 1);
// Increment edge count at this position
}
}
for (int count : edgesFrequency.values()) {
maxBrickEdges = Math.max(maxBrickEdges, count);
// Find the maximum count of brick edges at any position
}
return rows - maxBrickEdges;
// The minimum number of bricks that need to be cut
}
}Brick Wall Code in Python - Optimised
from collections import defaultdict
class Solution:
def leastBricks(self, wall: list[list[int]]) -> int:
rows = len(wall)
# Total number of rows (height of the wall)
max_brick_edges = 0
# HashMap to count brick edges at each position
edges_frequency = defaultdict(int)
for row in wall:
idx = 0
# Tracks the current edge position
for i in range(len(row) - 1):
idx += row[i]
# Move to the next edge position
edges_frequency[idx] += 1
# Increment edge count at this position
for count in edges_frequency.values():
max_brick_edges = max(max_brick_edges, count)
# Find the maximum count of brick edges at any position
return rows - max_brick_edges
# The minimum number of bricks that need to be cutBrick Wall Code in Javascript - Optimised
class Solution {
leastBricks(wall) {
let rows = wall.length;
// Total number of rows (height of the wall)
let maxBrickEdges = 0;
// HashMap to count brick edges at each position
let edgesFrequency = new Map();
for (let row of wall) {
let idx = 0;
// Tracks the current edge position
for (let i = 0; i < row.length - 1; i++) {
idx += row[i];
// Move to the next edge position
edgesFrequency.set(idx, (edgesFrequency.get(idx) || 0) + 1);
// Increment edge count at this position
}
}
for (let count of edgesFrequency.values()) {
maxBrickEdges = Math.max(maxBrickEdges, count);
// Find the maximum count of brick edges at any position
}
return rows - maxBrickEdges;
// The minimum number of bricks that need to be cut
}
}Time Complexity: O(n*m)
Iterating through the wall (O(n * m)) : We iterate over each row in wall → O(n) . For each row, we iterate over m-1 bricks (ignoring the last one) → O(m) , Thus, the total operations in this loop are O(n * m)
Finding the max brick edge frequency (O(n)) :We iterate through the edgesFrequency map, which at most has n unique positions (since there are at most n different edge positions) → O(n)
Final Complexity
- The dominant factor is O(n * m) from the first loop.
- The second loop runs in O(n), which is negligible compared to O(n * m).
- Final Time Complexity: O(n * m), where n is the number of rows and m is the average number of bricks in each row.
This approach should not cause TLE given the constraints. The expected time complexity is O(n * m), but practically it runs in O(n) due to efficient hashing.
Space Complexity: O(n)
Auxiliary Space Complexity
- The only extra data structure we use is an unordered_map (hash map) to store the frequency of brick edges.
- The number of unique brick edge positions is at most n - 1 (since we don’t count the last brick in each row).
- In the worst case, if all rows have unique edge positions, we store at most O(n) entries.
- Since an unordered_map requires additional space for handling collisions, its worst-case space complexity can be O(n), but on average, it remains close to O(n).
Thus, Auxiliary Space Complexity = O(n).
Total Space Complexity
Input Storage: The input wall consists of n rows, each with m_i bricks, and the sum of all bricks across rows is at most 2 × 10⁴.
- The space required for this input is O(∑ wall[i].length) = O(2 × 10⁴).
Extra Space: We already established that the extra space (unordered_map) is O(n).
Thus, Total Space Complexity = O(n + 2 × 10⁴) ≈ O(2 × 10⁴)
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given a wall of a specified height and width, where each row is built using bricks of fixed lengths, determine the number of ways to construct the wall such that no two adjacent rows have vertical seams aligned. You can use bricks of size 1xX, but they must fit exactly within the given width. How can you efficiently count the number of valid wall configurations while ensuring structural stability?