Brick Wall

medium array hash map

Problem

A vertical line cuts the brick wall. It crosses a brick if its position is inside (not at the edge). Find the line that crosses the fewest bricks. Return min bricks crossed.

Inputwall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]

Output2

Position-4 edge appears in 4 rows; min crossed = 6 − 4 = 2.

wall (rows ; -separated)

from collections import Counter
def least_bricks(wall):
    edges = Counter()
    for row in wall:
        x = 0
        for w in row[:-1]:
            x += w
            edges[x] += 1
    best = max(edges.values()) if edges else 0
    return len(wall) - best

function leastBricks(wall) {
  const edges = new Map();
  let best = 0;
  for (const row of wall) {
    let x = 0;
    for (let i = 0; i < row.length - 1; i++) {
      x += row[i];
      const c = (edges.get(x) || 0) + 1;
      edges.set(x, c);
      if (c > best) best = c;
    }
  }
  return wall.length - best;
}

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> edges = new HashMap<>();
        int best = 0;
        for (List<Integer> row : wall) {
            int x = 0;
            for (int i = 0; i < row.size() - 1; i++) {
                x += row.get(i);
                int c = edges.getOrDefault(x, 0) + 1;
                edges.put(x, c);
                best = Math.max(best, c);
            }
        }
        return wall.size() - best;
    }
}

int leastBricks(vector<vector<int>>& wall) {
    unordered_map<int, int> edges;
    int best = 0;
    for (auto& row : wall) {
        int x = 0;
        for (int i = 0; i + 1 < (int)row.size(); i++) {
            x += row[i];
            best = max(best, ++edges[x]);
        }
    }
    return (int)wall.size() - best;
}

Explanation

Instead of asking "which line crosses the fewest bricks", flip the question: a line crosses a brick only when it does not land on a gap between two bricks. So we want the line that passes through the most edges (gaps).

For each row we add up the brick widths from left to right. Every running total marks the position of an edge inside that row. We skip the very last brick because the far-right wall edge does not count. We drop each edge position into a hash map edges that counts how many rows share that exact gap.

The best line to draw sits at the gap shared by the most rows. If best is the largest count in the map, then the answer is len(wall) - best: every row whose gap is hit is spared, and the rest each lose one brick.

Example: with 6 rows, the gap at position 4 shows up in 4 of them, which is the maximum. So min bricks crossed = 6 - 4 = 2.

Because we only walk each brick once and hash-map lookups are instant, the whole thing runs in one pass over all the bricks.

Time: O(N) total bricks Space: O(N)