Brick Wall - Practice Coding Problems

Brick Wall - Problem

There is a rectangular brick wall in front of you with n rows of bricks. The i-th 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.

Input & Output

Example 1 — Standard Wall

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

› Output: 2

💡 Note: The wall has 6 rows. Drawing a vertical line at position 4 passes through edges of 4 rows, so it crosses only 2 bricks (6-4=2).

Example 2 — Single Column

$ Input: wall = [[1],[1],[1]]

› Output: 3

💡 Note: All rows have only one brick each, so any vertical line must cross all 3 bricks. No edges exist except at boundaries.

Example 3 — Perfect Alignment

$ Input: wall = [[2,1],[2,1],[2,1]]

› Output: 0

💡 Note: All rows have an edge at position 2, so we can draw a line there that crosses 0 bricks.

Constraints

n == wall.length
1 ≤ n ≤ 10⁴
1 ≤ wall[i].length ≤ 10⁴
1 ≤ sum(wall[i].length) ≤ 2 × 10⁴
1 ≤ wall[i][j] ≤ 2³¹ - 1
For each row i, sum(wall[i]) is the same.

Visualization

Tap to expand

Understanding the Visualization

Input Wall

2D array representing brick widths in each row

Find Edges

Calculate where bricks end in each row

Optimal Cut

Cut at position with most aligned edges

Key Takeaway

🎯 Key Insight: The best cut line passes through the most brick edge positions (seams between bricks)

Asked in

f Facebook 35 G Google 28 a Amazon 22 M Microsoft 18

The key insight is that to minimize crossed bricks, we should find the vertical position where the most brick edges align. Using a hash map to count edge frequencies gives us O(n×m) time complexity. The answer is total_rows - max_edge_frequency.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Count Edge Positions	O(n × m)	O(w)	Count frequency of brick edge positions, find most common edge
Brute Force - Try Every Position	O(n × w)	O(1)	Check every possible vertical position and count bricks crossed

Hash Map - Count Edge Positions — Algorithm Steps

Calculate prefix sums to find all edge positions
Count frequency of each edge position
Find position with maximum edges
Return n - max_edges

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Edges

Find cumulative positions where bricks end

Count Frequencies

Track how often each edge position appears

Find Maximum

Position with most edges gives minimum crosses

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_EDGES 1000

int solution(int** wall, int wallSize, int* wallColSize) {
    if (wallSize == 0) return 0;
    
    // Simple array-based counting (assuming reasonable edge positions)
    int edgeCount[MAX_EDGES] = {0};
    int maxPos = 0;
    
    // Count frequency of edge positions
    for (int i = 0; i < wallSize; i++) {
        int edgePos = 0;
        // Don't include the last edge (wall boundary)
        for (int j = 0; j < wallColSize[i] - 1; j++) {
            edgePos += wall[i][j];
            if (edgePos < MAX_EDGES) {
                edgeCount[edgePos]++;
                if (edgePos > maxPos) maxPos = edgePos;
            }
        }
    }
    
    // Find maximum edges at any position
    int maxEdges = 0;
    for (int i = 0; i <= maxPos; i++) {
        if (edgeCount[i] > maxEdges) {
            maxEdges = edgeCount[i];
        }
    }
    
    // Return minimum crossed bricks
    return wallSize - maxEdges;
}

int main() {
    // Simple parsing for demo
    int wall1[] = {1, 2, 2, 1};
    int wall2[] = {3, 1, 2};
    int wall3[] = {1, 3, 2};
    int wall4[] = {2, 4};
    int wall5[] = {3, 1, 1, 1};
    int wall6[] = {1, 1, 2, 2};
    
    int* wall[] = {wall1, wall2, wall3, wall4, wall5, wall6};
    int wallColSize[] = {4, 3, 3, 2, 4, 4};
    
    printf("%d\n", solution(wall, 6, wallColSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

Iterate through all bricks in all rows once to build edge frequency map

✓ Linear Growth

Space Complexity

O(w)

Hash map stores at most w edge positions where w is wall width

✓ Linear Space

87.0K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - Count Edge Positions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler