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 cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.
Given the 2D array wall that contains the information about the wall, return the minimum number of crossed bricks after drawing such a vertical line.
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
Example 2:
Input: wall = [[1],[1],[1]] Output: 3
Constraints:
n == wall.length1 <= n <= 1041 <= wall[i].length <= 1041 <= sum(wall[i].length) <= 2 * 104sum(wall[i]) is the same for each row i.1 <= wall[i][j] <= 231 - 1This approach leverages the concept of 'prefix sum' where we keep a running sum across each row to determine the edges of bricks. We use a HashMap to count occurrences of these edges as potential positions to draw a line that crosses the minimum number of bricks.
The provided Python solution employs a defaultdict to accumulate the frequency of edge positions encountered while computing the prefix sum for each brick within the rows. The goal is to find a position with the maximum edge count because this minimizes the number of bricks cut, given that the line will pass through these edges.
Time Complexity: O(m), where m is the total number of bricks. We iterate over each brick except the last one for every row resulting in a time proportional to the number of bricks.
Space Complexity: O(width), where width represents the total width of rows. Edge positions are stored in the map, and their count can scale with the width.
This alternative approach introduces a dynamic programming solution where instead of counting edges, we explore all positions by keeping track of the position sum as a state. The goal is to dynamically compute and avoid unnecessary recomputation of the edge frequencies.
This Java solution exemplifies a similar logic to the Python solution but makes use of Java collections, such as HashMap, to track and update edge counts as the prefix sums are computed. This helps find the cutting position that crosses the fewest bricks.
Time Complexity: O(m), where m is the total number of bricks. This involves iterating through most of the bricks.
Space Complexity: O(width), where width represents the total width of rows. The storage complexity of the HashMap is proportional to how many distinct prefix sums are processed.
The core idea of this approach is to find the vertical line that crosses the least number of bricks by looking at the position where the most number of brick edges align vertically. We can achieve this by computing prefix sums for each row, except for the last brick in each row. A hashmap (or dictionary) is used to keep track of how often each prefix sum occurs.
The C implementation uses an array to simulate a hashmap for counting the number of times a prefix sum occurs. This helps in finding the position with the most edges, which allows determining the vertical line with the least number of bricks crossed.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m), where n is the number of rows and m is the average number of bricks per row.
Space Complexity: O(n * m), due to the auxiliary data structure holding prefix sums.
| Approach | Complexity |
|---|---|
| Prefix Sum and HashMap | Time Complexity: O(m), where m is the total number of bricks. We iterate over each brick except the last one for every row resulting in a time proportional to the number of bricks. |
| Dynamic Programming Approach | Time Complexity: O(m), where m is the total number of bricks. This involves iterating through most of the bricks. |
| Prefix Sum with HashMap | Time Complexity: O(n * m), where n is the number of rows and m is the average number of bricks per row. |
Brick Wall - Leetcode 554 - Python • NeetCode • 26,042 views views
Watch 9 more video solutions →Practice Brick Wall with our built-in code editor and test cases.
Practice on FleetCode