What is the time complexity of Brick Wall?

The optimal solution has a time complexity of O(R * B).

What data structures are used to solve Brick Wall?

This problem uses Array, Hash Table. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Brick Wall?

Insight 1: The problem is equivalent to finding the horizontal gap between bricks that appears most frequently across all rows. A line drawn through this gap will cross the fewest bricks. Insight 2: A hash table (or dictionary) is essential to efficiently count the occurrences of each gap position.

Which companies ask LeetCode 554. Brick Wall in interviews?

This problem is frequently asked at Agoda, Trexquant.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Brick Wall - LeetCode 554 Solution

Brick Wall - Complete Solution Guide

Brick Wall is LeetCode problem 554, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

There is a rectangular brick wall in front of you with n rows of bricks. The i th 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 cannot draw a line just along one of the two vertical edges of the wall, in which case the line w

Detailed Explanation

The problem asks us to find the minimum number of bricks crossed by a vertical line drawn from the top to the bottom of a brick wall. The wall is represented by a 2D array where each row contains the widths of the bricks in that row. The key rule is that if the line goes through the edge of a brick (i.e., the boundary between two bricks), the brick is *not* considered crossed. We must find the vertical line that crosses the fewest bricks, avoiding drawing the line along the edges of the wall.

Solution Approach

The solution iterates through each row of the wall, calculating the cumulative width at each gap between bricks. It uses a hash table (`gaps_count`) to store the frequency of each gap position. After processing all rows, the algorithm finds the gap position with the highest frequency (`max_gaps`). The minimum number of crossed bricks is then calculated as the total number of rows minus `max_gaps`. This works because `max_gaps` represents the number of rows where the chosen vertical line avoids crossing a brick.

Step-by-Step Algorithm

Step 1: Initialize a hash table (or dictionary) `gaps_count` to store the number of times each gap position appears.
Step 2: Initialize `max_gaps` to 0. This variable will keep track of the maximum number of times any gap position appears.
Step 3: Iterate through each row in the `wall`.
Step 4: For each row, initialize `position` to 0. This variable will track the cumulative width as we iterate through the bricks in the row.
Step 5: Iterate through the bricks in the row *except* for the last brick. This is because a gap after the last brick is not a valid place to draw the line.
Step 6: Add the current brick's width to `position` to update the cumulative width.
Step 7: Update the `gaps_count` hash table. Increment the count for the current `position` (gap). If the gap doesn't exist, add it with a count of 1.
Step 8: Update `max_gaps` to be the maximum value between the current `max_gaps` and the count of the current `position` in `gaps_count`.
Step 9: After processing all rows, return the number of rows in the wall minus `max_gaps`. This is the minimum number of bricks crossed.
Step 10: C specific version of solution avoids usage of hashmap to improve performance. Here number of possible gaps is limited so we use fixed-size array to keep track of gap counts

Key Insights

Insight 1: The problem is equivalent to finding the horizontal gap between bricks that appears most frequently across all rows. A line drawn through this gap will cross the fewest bricks.
Insight 2: A hash table (or dictionary) is essential to efficiently count the occurrences of each gap position.
Insight 3: The width of the wall is constant across all rows, so we only need to consider gap positions up to this width.
Insight 4: We only need to calculate the cumulative width up to the second-to-last brick in each row because a gap after the last brick is equivalent to a line drawn on the edge of the wall which is not allowed.

Complexity Analysis

Time Complexity: O(R * B)

Space Complexity: O(W)

Topics

This problem involves: Array, Hash Table.

Companies

Asked at: Agoda, Trexquant.

Brick Wall | LeetCode 554

Medium

Array Hash Table

Time: O(R * B)Space: O(W)

Solution Code

Available in:

import java.util.HashMap;
import java.util.List;
import java.util.Map;

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

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 554: Brick Wall - Detailed explanation and solution approaches.

Topics

Array Hash Table

Companies

AgodaTrexquant

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:554

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Initialize a hash table (or dictionary) `gaps_count` to store the number of times each gap position appears.
2
Step 2: Initialize `max_gaps` to 0. This variable will keep track of the maximum number of times any gap position appears.
3
Step 3: Iterate through each row in the `wall`.
4
Step 4: For each row, initialize `position` to 0. This variable will track the cumulative width as we iterate through the bricks in the row.
5
Step 5: Iterate through the bricks in the row *except* for the last brick. This is because a gap after the last brick is not a valid place to draw the line.
6
Step 6: Add the current brick's width to `position` to update the cumulative width.
7
Step 7: Update the `gaps_count` hash table. Increment the count for the current `position` (gap). If the gap doesn't exist, add it with a count of 1.
8
Step 8: Update `max_gaps` to be the maximum value between the current `max_gaps` and the count of the current `position` in `gaps_count`.
9
Step 9: After processing all rows, return the number of rows in the wall minus `max_gaps`. This is the minimum number of bricks crossed.
10
Step 10: C specific version of solution avoids usage of hashmap to improve performance. Here number of possible gaps is limited so we use fixed-size array to keep track of gap counts

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(R * B)

💾

Space Complexity

O(W)

📝

Why?

The time complexity is determined by the nested loops iterating through the rows and bricks. The space complexity is determined by the size of the hash table, which stores the gap counts. In the worst case, the number of unique gap positions can be equal to the width of the wall.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using an Array (C version)

Instead of using a hash table, we can use an array to store the counts of the gaps. This works efficiently if the maximum width of the wall is relatively small (e.g., less than 10000 as used in C implementation). It avoids hash function overhead.

Time: O(R * B), where R is the number of rows and B is the maximum number of bricks in a row.Space: O(W), where W is the total width of the wall (the size of the array).

Trade-offs: Using an array is faster in practice due to the avoidance of hash table lookups but requires knowing (or estimating) the maximum width in advance. If the wall width is unknown or potentially very large, a hash table is more appropriate.

✨

Key Insights

1Insight 1: The problem is equivalent to finding the horizontal gap between bricks that appears most frequently across all rows. A line drawn through this gap will cross the fewest bricks.
2Insight 2: A hash table (or dictionary) is essential to efficiently count the occurrences of each gap position.
3Insight 3: The width of the wall is constant across all rows, so we only need to consider gap positions up to this width.
4Insight 4: We only need to calculate the cumulative width up to the second-to-last brick in each row because a gap after the last brick is equivalent to a line drawn on the edge of the wall which is not allowed.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: Empty wall (wall with no rows). The code should handle this gracefully and return 0. Although constraints mention `1 <= n <= 10^4`, it's good to be aware.
Edge case 2: A wall where all rows have only one brick. In this case, there are no gaps between bricks and all vertical lines will cross all bricks in each row. The `max_gaps` will be 0, and the result will be the number of rows.
Edge case 3: The wall is consistent, but a single row could have all bricks of width 1. The algorithm correctly handles cases of multiple gaps.
Edge case 4: All rows are exactly the same. Then the `max_gaps` is wall.length - no_crossed_bricks. The number of crossings will then be minimal

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Including the gap after the last brick in each row. This is incorrect because the problem states that a line drawn along the edge of the wall crosses no bricks, so it is an invalid line.

✗Common mistake 2: Not handling the case where a row contains only one brick. This leads to an empty row, and therefore, `max_gaps` is always 0, which leads to the wrong answer.

✗Common mistake 3: Confusing the calculation of `max_gaps`. The correct approach is to find the maximum number of times a gap position appears, not the maximum gap value itself.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Optimizing the placement of support beams in a building to minimize the number of structural elements crossed.

🏦Real-world scenario 2: Determining the optimal location for a fence to minimize the number of obstacles (trees, rocks) it crosses.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 15, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Brick Wall"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?