What is the primary pattern used to solve the Brick Wall problem?

The problem is typically solved using array scanning combined with hash table lookups to track cumulative brick edges and minimize the number of crossed bricks.

How do hash tables help in solving the Brick Wall problem?

Hash tables allow us to efficiently track the positions of brick edges across rows, helping us find the most optimal vertical line with minimal crossings.

Can the Brick Wall problem be solved using brute force?

While a brute force solution is possible, it is inefficient and doesn't scale well. The optimal solution uses hash tables to avoid excessive computations.

What are the time and space complexities of the Brick Wall solution?

The time complexity is O(n * m), where n is the number of rows and m is the average number of bricks per row. Space complexity is O(m).

What are some common mistakes when solving the Brick Wall problem?

Common mistakes include inefficient brute force methods, mishandling edge cases where the line is at the vertical edge, and incorrect brick alignment handling.

#554

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

砖墙

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。你现在要画一条自顶向下的、穿过最少砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。 …

数组哈希表

题目描述

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。

你现在要画一条 自顶向下 的、穿过最少砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。

示例 1：

输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出：2

示例 2：

输入：wall = [[1],[1],[1]]
输出：3

提示：

n == wall.length
1 <= n <= 10⁴
1 <= wall[i].length <= 10⁴
1 <= sum(wall[i].length) <= 2 * 10⁴
对于每一行 i ，sum(wall[i]) 是相同的
1 <= wall[i][j] <= 2³¹ - 1

lightbulb

解题思路

方法一：哈希表 + 前缀和

我们可以用一个哈希表 $\textit{cnt}$ 记录每一行除了最后一个砖块以外的前缀和，其中键为前缀和的值，值为该前缀和出现的次数。

遍历每一行，对于当前行的每一个砖块，我们将其加到当前的前缀和上，然后更新 $\textit{cnt}$ 。

最后我们遍历 $\textit{cnt}$ ，找出出现次数最多的前缀和，这就是穿过的砖块数量最少的情况。最后答案即为砖墙的行数减去穿过的砖块数量。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(n)$ 。其中 $m$ 和 $n$ 分别是砖墙的行数和砖墙的砖块数。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        cnt = Counter()
        for row in wall:
            s = 0
            for x in row[:-1]:
                s += x
                cnt[s] += 1
        return len(wall) - max(cnt.values(), default=0)

speed

复杂度分析

指标	值
时间	complexity is O(n * m), where n is the number of rows and m is the average number of bricks per row. Space complexity is O(m) for storing the cumulative sums of brick edges in the hash map.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for familiarity with array scanning and hash table usage.
question_mark
Candidates should demonstrate understanding of how to efficiently track cumulative sums and minimize intersections.
question_mark
Watch for performance considerations when handling large inputs, as the problem constraints require optimal space and time solutions.

warning

常见陷阱

外企场景

error
Overlooking edge cases where the line goes along the vertical edge of the wall, which leads to 0 crossed bricks.
error
Inefficient solution using brute force rather than hash map lookups for cumulative positions.
error
Incorrectly handling cases where all bricks are aligned in a single column or row, leading to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem by limiting the number of rows or columns to test edge cases for performance.
arrow_right_alt
Allow for non-rectangular walls where row widths may differ, increasing complexity in cumulative tracking.
arrow_right_alt
Change the problem to focus on drawing a horizontal line instead, requiring a different scanning pattern and data structure.

help

常见问题

外企场景

继续练习

#560 和为 K 的子数组 #575 分糖果 #532 数组中的 k-diff 数对