LeetCode 554: Brick Wall Solution

Master LeetCode problem 554 (Brick Wall), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

554. Brick Wall

Medium

Array Hash Table

Problem Explanation

Explanation

To find the minimum number of crossed bricks after drawing a vertical line, we need to determine the positions where the vertical line crosses the least number of bricks. We can achieve this by keeping track of the positions where the edges of the bricks occur. The most common edge position will be the optimal position for the vertical line.

Create a hash map to store the occurrence of edge positions.
Iterate through each row of the wall and keep track of the edge positions.
Find the most common edge position.
Calculate the number of crossed bricks based on the frequency of the common edge position.

Time Complexity: O(n * m) where n is the number of rows and m is the average number of bricks in each row. Space Complexity: O(m) where m is the total number of unique edge positions.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 554 (Brick Wall)?

This page provides optimized solutions for LeetCode problem 554 (Brick Wall) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 554 (Brick Wall)?

The time complexity for LeetCode 554 (Brick Wall) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 554 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 554 in Java, C++, or Python.

Back to LeetCode Solutions