algoadvance

Leetcode 554. Brick Wall

Problem Statement

You are given a 2D array wall representing a brick wall. Each row in the wall array is an array of positive integers representing the widths of bricks in that row, from left to right. Your goal is to find the minimum number of vertical lines drawn through the entire wall (from top to bottom) that cross the fewest bricks.

For example: If the input is:

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

The output should be 2.

Clarifying Questions

1. Are the widths of the bricks always positive integers? Yes, the brick widths are always positive integers.

2. Is the wall always rectangular, height-wise? Yes, each row in the wall may have different numbers of bricks, but the total width of bricks in each row is always the same.

3. Should we focus on cutting through the least number of bricks or not cutting through any bricks at all if possible? The goal is to minimize the number of bricks cut through.

Strategy

1. Calculate Brick Edges:
   • We need to keep a track of where the edges of the bricks (not including the final edge on the right) fall in each row.
2. Use a HashMap:
   • Use a HashMap to store the count of occurrences of each edge position. The key will be the edge position, and the value will be the number of rows that have this edge position.
3. Compute Minimum Cuts:
   • Find the edge position that appears the most. The most common edge position will denote the line that crosses the fewest bricks if drawn.
   • Subtract this maximum occurrence from the total number of rows to get the minimum number of bricks crossed.

Code Implementation

import java.util.*;

public class BrickWall {
    public int leastBricks(List<List<Integer>> wall) {
        HashMap<Integer, Integer> edgeCount = new HashMap<>();
        int maxEdgeCount = 0;
        
        // Calculate edge positions
        for (List<Integer> row : wall) {
            int width = 0;
            // Exclude the last brick since we should not consider the edge of the wall itself
            for (int i = 0; i < row.size() - 1; i++) {
                width += row.get(i);
                edgeCount.put(width, edgeCount.getOrDefault(width, 0) + 1);
                maxEdgeCount = Math.max(maxEdgeCount, edgeCount.get(width));
            }
        }
        
        return wall.size() - maxEdgeCount;
    }

    public static void main(String[] args) {
        BrickWall solution = new BrickWall();
        List<List<Integer>> wall = Arrays.asList(
            Arrays.asList(1, 2, 2, 1),
            Arrays.asList(3, 1, 2),
            Arrays.asList(1, 3, 2),
            Arrays.asList(2, 4),
            Arrays.asList(3, 1, 2),
            Arrays.asList(1, 3, 1, 1)
        );
        
        System.out.println(solution.leastBricks(wall)); // Output: 2
    }
}

Time Complexity

• Time Complexity: O(N * M), where N is the number of rows in the wall and M is the maximum number of bricks in any row. We iterate through each brick in each row exactly once.
• Space Complexity: O(N), for storing the edge positions and their counts in the HashMap, where N is the total number of distinct edges.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?