Domain 2MediumCORE

Brick Wall

We are given a wall represented by rows of bricks, each with specific widths. We need to draw a vertical line from top to bottom that crosses the minimum number of brick faces (crossing an edge is free). The constraint is we cannot align our line exactly at the very left or right boundary of the entire wall structure; it must pass through internal gaps if possible.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table

554. Brick Wall

Model: qwen3.5:9b
Topics: Hash Table
FAANG asked: 0
Acceptance rate: 50.8%


Problem Breakdown

We are given a wall represented by rows of bricks, each with specific widths. We need to draw a vertical line from top to bottom that crosses the minimum number of brick faces (crossing an edge is free). The constraint is we cannot align our line exactly at the very left or right boundary of the entire wall structure; it must pass through internal gaps if possible.

Inputs: A list of lists (wall), where each inner list contains integers representing brick widths for that row. Output: An integer representing the minimum number of crossed bricks. Constraints & Edge Cases:

  • All rows have the same total width (the wall is rectangular).
  • We cannot draw at x=0x=0 or x=total_widthx=\text{total\_width}.
  • If a row has only one brick, there are no internal edges in that row to align with.
  • The map of edge positions might be empty if every row consists of a single wide brick (or similar configuration where no shared boundaries exist). In this case, we cross all rows regardless of line position.

Intuition

A brute-force approach would iterate through every possible horizontal coordinate from 11 to total_width−1\text{total\_width} - 1. For each coordinate, we count how many times it appears as a boundary across the wall (excluding start/end). Then we subtract that max frequency from total rows. However, iterating all coordinates is inefficient if widths are large (O(Width)×O(Rows))O(\text{Width}) \times O(\text{Rows})), which violates time constraints given NN up to 20,000 bricks and potentially larger width sums.

The key insight is recognizing this as a frequency counting problem on cumulative positions. We don’t need to check every coordinate; we only care about the coordinates where edges actually exist in at least one row. If many rows share an edge at position XX, drawing our line there minimizes crossings for those specific rows (crossing 0 bricks). The total crossed is simply Total Rows - Max Edges Aligned.

Approach

  1. Initialize a hash map (edges) to store the frequency of each internal boundary coordinate found across all rows.
  2. Iterate through every row in the wall.
  3. For each row, maintain a running cumulative sum representing the current edge position from the left side of that specific row (which aligns with global x=0x=0).
  4. Add brick widths to this accumulator for every brick except the last one in the row. The rightmost boundary of any row is always at total_width, which we ignore per problem constraints.
  5. Increment the count in our map for each valid internal edge position encountered.
  6. After processing all rows, find the maximum frequency stored in the hash map (max_edges). If no edges were found (map empty), treat max as 0.
  7. Return len(wall) - max_edges.

Complexity Analysis

  • Time: O(N)O(N) where NN is the total number of bricks across all rows. We iterate through each brick exactly once to compute cumulative positions and update the map. Map operations are average O(1)O(1).
  • Space: O(K)O(K), where KK is the maximum possible distinct internal edge coordinates found in a single row (bounded by total width). In worst case, this could be proportional to input size (NN), as each brick can contribute at most one unique position.

Solution

from collections import defaultdict

def leastBricks(wall):
    # Map stores frequency of each cumulative width position across all rows
    edges = defaultdict(int)
    
    for row in wall:
        current_pos = 0
        
        # Iterate through bricks, stopping before the last one to find internal boundaries.
        # We avoid slicing (row[:-1]) to prevent creating a new list copy per row 
        # and instead check index or iterate directly with condition logic if needed.
        # Here we use enumerate and skip the final iteration implicitly by checking length.
        for i, brick_width in enumerate(row):
            current_pos += brick_width
            
            # Do not count the edge at total width (end of wall) as an internal gap alignment option
            if i < len(row) - 1: 
                edges[current_pos] += 1
                
    if not edges:
        return len(wall)
    
    max_edges_aligned = max(edges.values())
    # Minimum crossed bricks is total rows minus the best alignment of gaps
    return len(wall) - max_edges_aligned

# Example usage based on problem description (for verification only, typically omitted in submission box)
input_wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
print(leastBricks(input_wall)) # Output: 2

Edge Cases Handled

  • No internal edges: If every row is a single brick (e.g., [[5], [6]]), the loop condition skips adding to map. The map remains empty, and we return len(wall), correctly indicating we must cross every row regardless of line position.
  • Single Row Wall: Logic holds; if one row has internal edges, max_edges > 0, reducing crossings to 1 (if possible). If single brick per row in a multi-row wall, handled above.
  • Large Widths: Python handles arbitrary precision integers automatically, so current_pos overflow is not an issue even with large sums exceeding standard integer limits of other languages.