554. Brick Wall

Problem Description

There is a rectangular brick wall in front of you with n rows of bricks. The ith 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 need to find out how many bricks are crossed by your line in the best case.

Example 1:

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2
Explanation: The vertical line can be drawn at x = 2.

Example 2:

Input: wall = [[1],[1],[1]]
Output: 3

Constraints:

• n == wall.length
• 1 <= n <= 10⁴
• 1 <= wall[i].length <= 10⁴
• 1 <= sum(wall[i].length) <= 2 * 10⁴
• sum(wall[i]) is the same for each row i
• 1 <= wall[i][j] <= 2³¹ - 1

Python Solution

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        edges = defaultdict(int)
        
        # Count the frequency of edges at each position
        for row in wall:
            pos = 0
            for brick in row[:-1]:  # Skip the last brick in each row
                pos += brick
                edges[pos] += 1
        
        # If no edges found, return the height of the wall
        if not edges:
            return len(wall)
        
        # Return wall height minus the maximum frequency of edges
        return len(wall) - max(edges.values())

Java Solution

class Solution {
    public int leastBricks(List> wall) {
        Map edges = new HashMap<>();
        
        // Count the frequency of edges at each position
        for (List row : wall) {
            int pos = 0;
            for (int i = 0; i < row.size() - 1; i++) {  // Skip the last brick
                pos += row.get(i);
                edges.put(pos, edges.getOrDefault(pos, 0) + 1);
            }
        }
        
        // If no edges found, return the height of the wall
        if (edges.isEmpty()) {
            return wall.size();
        }
        
        // Return wall height minus the maximum frequency of edges
        int maxEdges = Collections.max(edges.values());
        return wall.size() - maxEdges;
    }
}

C++ Solution

class Solution {
public:
    int leastBricks(vector>& wall) {
        unordered_map edges;
        
        // Count the frequency of edges at each position
        for (const auto& row : wall) {
            int pos = 0;
            for (int i = 0; i < row.size() - 1; i++) {  // Skip the last brick
                pos += row[i];
                edges[pos]++;
            }
        }
        
        // If no edges found, return the height of the wall
        if (edges.empty()) {
            return wall.size();
        }
        
        // Return wall height minus the maximum frequency of edges
        int maxEdges = 0;
        for (const auto& [pos, count] : edges) {
            maxEdges = max(maxEdges, count);
        }
        return wall.size() - maxEdges;
    }
};

JavaScript Solution

/**
 * @param {number[][]} wall
 * @return {number}
 */
var leastBricks = function(wall) {
    const edges = new Map();
    
    // Count the frequency of edges at each position
    for (const row of wall) {
        let pos = 0;
        for (let i = 0; i < row.length - 1; i++) {  // Skip the last brick
            pos += row[i];
            edges.set(pos, (edges.get(pos) || 0) + 1);
        }
    }
    
    // If no edges found, return the height of the wall
    if (edges.size === 0) {
        return wall.length;
    }
    
    // Return wall height minus the maximum frequency of edges
    const maxEdges = Math.max(...edges.values());
    return wall.length - maxEdges;
};

C# Solution

public class Solution {
    public int LeastBricks(IList> wall) {
        Dictionary edges = new Dictionary();
        
        // Count the frequency of edges at each position
        foreach (var row in wall) {
            int pos = 0;
            for (int i = 0; i < row.Count - 1; i++) {  // Skip the last brick
                pos += row[i];
                if (!edges.ContainsKey(pos)) {
                    edges[pos] = 0;
                }
                edges[pos]++;
            }
        }
        
        // If no edges found, return the height of the wall
        if (edges.Count == 0) {
            return wall.Count;
        }
        
        // Return wall height minus the maximum frequency of edges
        int maxEdges = edges.Values.Max();
        return wall.Count - maxEdges;
    }
}