Brick Wall

Published at24 Jul 2026

Like0

There is a rectangular brick wall with rows of bricks. The bricks in each row have various integer widths. You want to draw a vertical line from the top to the bottom that cuts through the fewest number of bricks. The line must go through the wall between two adjacent bricks at the same horizontal position across every row. Bricks on the edges (at position 0 and at the total width) do not count as cuts.

A brute force approach would check every possible horizontal position between bricks in the first row. But a hash map makes this efficient: count how many rows have a brick edge at each position. For each row, compute prefix sums of brick widths — these are the edge positions where a blank row has its gaps. Increment a counter in the hash map for each edge position (excluding the total width, which is the wall's right edge).

The vertical line that cuts through the fewest bricks is the position with the most edge alignments. Since each row has exactly one gap at each edge position, if N rows have an edge at position x, then a line at x cuts through (wall height - N) bricks. The answer is simply the height of the wall minus the maximum count from the hash map.

Edge cases include a wall with a single row of one brick (the line must cut that brick since there are no gaps), and a wall where all rows have the same brick arrangement (the optimal line goes through the shared gap).

Example Input & Output

Example 1

Input

[[1],[1],[1]]

Output

Explanation

No edges except ends, so cut must go through all 3 bricks.

Example 2

Input

[[1,2],[1,2],[1,2]]

Output

Explanation

Position 1 has edges in all rows, so cut = 3-3 = 0.

Example 3

Input

[[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]

Output

Explanation

Most edges at position 3 (rows 2,3,5), so cut = 6-4 = 2 bricks.

Example 4

Input

[[1,1],[1,1],[1,1]]

Output

Explanation

Position 1 has edges in all rows.

Example 5

Input

[[2,1],[1,2]]

Output

Explanation

No shared edge position. Best is 1 row aligned, so cut = 2-1 = 1.

Algorithm Flow

Recommendation Algorithm Flow for Brick Wall

Solution Approach

Compute prefix sums for each row. Store edge position frequencies in a hash map. The answer is height - max frequency (or height if no edge aligns).

function solution(wall) {
  var freq = {};
  var best = 0;
  for (var i = 0; i < wall.length; i++) {
    var sum = 0;
    for (var j = 0; j < wall[i].length - 1; j++) {
      sum += wall[i][j];
      freq[sum] = (freq[sum] || 0) + 1;
      if (freq[sum] > best) best = freq[sum];
    }
  }
  return wall.length - best;
}

Time O(N * M) where N=rows, M=bricks per row. Space O(total edge positions).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int solution(int[][] wall) {
        Map<Integer,Integer> freq = new HashMap<>();
        int best = 0;
        for (int[] row : wall) {
            int sum = 0;
            for (int i = 0; i < row.length - 1; i++) {
                sum += row[i];
                int val = freq.getOrDefault(sum, 0) + 1;
                freq.put(sum, val);
                if (val > best) best = val;
            }
        }
        return wall.length - best;
    }
}

javascript

function solution(wall) {
  var freq = {};
  var best = 0;
  for (var i = 0; i < wall.length; i++) {
    var sum = 0;
    for (var j = 0; j < wall[i].length - 1; j++) {
      sum += wall[i][j];
      freq[sum] = (freq[sum] || 0) + 1;
      if (freq[sum] > best) best = freq[sum];
    }
  }
  return wall.length - best;
}

php

<?php
function solution($wall) {
    $freq = [];
    $best = 0;
    foreach ($wall as $row) {
        $sum = 0;
        for ($i = 0; $i < count($row) - 1; $i++) {
            $sum += $row[$i];
            $freq[$sum] = ($freq[$sum] ?? 0) + 1;
            if ($freq[$sum] > $best) $best = $freq[$sum];
        }
    }
    return count($wall) - $best;
}

python

def solution(wall):
    freq = {}
    best = 0
    for row in wall:
        s = 0
        for brick in row[:-1]:
            s += brick
            freq[s] = freq.get(s, 0) + 1
            if freq[s] > best:
                best = freq[s]
    return len(wall) - best

rust

use std::collections::HashMap;
fn solution(wall: Vec<Vec<i32>>) -> i32 {
    let mut freq: HashMap<i32, i32> = HashMap::new();
    let mut best = 0i32;
    for row in &wall {
        let mut sum = 0i32;
        for i in 0..row.len()-1 {
            sum += row[i];
            let val = freq.get(&sum).unwrap_or(&0) + 1;
            freq.insert(sum, val);
            if val > best { best = val; }
        }
    }
    wall.len() as i32 - best
}

typescript

function solution(wall: number[][]): number {
    var freq: any = {};
    var best = 0;
    for (var i = 0; i < wall.length; i++) {
        var sum = 0;
        for (var j = 0; j < wall[i].length - 1; j++) {
            sum += wall[i][j];
            freq[sum] = (freq[sum] || 0) + 1;
            if (freq[sum] > best) best = freq[sum];
        }
    }
    return wall.length - best;
}

Related Hash Table Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Brick Wall

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Hash Table Challenges

Duplicate Indices Map

Contains Duplicate

Valid Anagram

Ransom Note

Two Sum Indices

Majority Element

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.