## 554. Brick Wall

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

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.

Example:

```Input:
[[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]
Output: 2
Explanation: ```

Note:

1. The width sum of bricks in different rows are the same and won't exceed INT_MAX.
2. The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won't exceed 20,000.

b'
\n\n

## Solution

\n
\n

#### Approach #1 Brute Force [Time Limit Exceeded]

\n

In this approach, we consider the given wall as being made up of virtual bricks each of width 1. We traverse over the width of the wall only in terms of these virtual bricks.

\n

Firstly, we need to determine the total number of virtual bricks. For this, we determine the width of the given wall by summing up the widths of the bricks in the first row. This width is stored in . Thus, we need to traverse over the widthe times now in terms of 1 unit in each iteration.

\n

We traverse over the virtual bricks in a column by column fashion. For keeping a track of the actual position at which we are currently in any row, we make use of a array. refers to the index of the brick in the row, which is being treated as the virtual brick in the current column\'s traversal. Further, we maintain a variable to keep a track of the number of bricks cut if we draw a line down at the current position.

\n

For every row considered during the column-by-column traversal, we need to check if we\'ve hit an actual brick boundary. This is done by updating the brick\'s width after the traversal. If we don\'t hit an actual brick boundary, we need to increment to reflect that drawing a line at this point leads to cutting off 1 more brick. But, if we hit an actual brick boundary, we increment the value of , with referring to the current row\'s index. But, now if we draw a line down through this boundary, we need not increment the .

\n

We repeat the same process for every column of width equal to a virtual brick, and determine the minimum value of obtained from all such traversals.

\n

The following animation makes the process clearer:

\n\n

!?!../Documents/554_Brick_Wall1.json:866,487!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . We traverse over the width() of the wall times, where is the height of the wall.

\n
• \n
• \n

Space complexity : . array of size is used, where is the height of the wall.

\n
• \n
\n
\n

#### Approach #2 Better Brute Force[Time LImit Exceeded]

\n

Algorithm

\n

In this approach, instead of traversing over the columns in terms of 1 unit each time, we traverse over the columns in terms of the width of the smallest brick encountered while traversing the current column. Thus, we update array and appropriately depending on the width of the smallest brick. Rest of the process remains the same as the first approach.

\n

The optimization achieved can be viewed by considering this example:

\n
`[[100, 50, 50],\n[50, 100],\n]\n`
\n

In this case, we directly jump over the columns in terms of widths of 50 units each time, rather than making traversals over widths incrementing by 1 unit each time.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . In worst case, we traverse over the length() of the wall times, where is the height of the wall.

\n
• \n
• \n

Space complexity : . array of size is used, where is the height of the wall.

\n
• \n
\n
\n

#### Approach #3 Using HashMap [Accepted]

\n

Algorithm

\n

In this approach, we make use of a HashMap which is used to store entries in the form: . Here, refers to the cumulative sum of the bricks\' widths encountered in the current row, and refers to the number of times the corresponding sum is obtained. Thus, in a way, represents the positions of the bricks\'s boundaries relative to the leftmost boundary.

\n

Let\'s look at the process first. We traverse over every row of the given wall. For every brick considered, we find the corresponding to the sum of the bricks\' widths encountered so far in the current row. If this \'s entry doesn\'t exist in the , we create a corresponding entry with an initial of 1. If the already exists as a key, we increment its corresponding value.

\n

This is done based on the following observation. We will never obtain the same value of twice while traversing over a particular row. Thus, if the value is repeated while traversing over the rows, it means some row\'s brick boundary coincides with some previous row\'s brick boundary. This fact is accounted for by incrementing the corresponding value.

\n

But, for every row, we consider the sum only upto the second last brick, since the last boundary isn\'t a valid boundary for the solution.

\n

At the end, we can obtain the maximum value to determine the minimum number of bricks that need to be cut to draw a vetical line through them.

\n

The following animation makes the process clear:

\n\n

!?!../Documents/554_Brick_Wall2.json:866,487!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . We traverse over the complete bricks only once. is the total number of bricks in a wall.

\n
• \n
• \n

Space complexity : . will contain atmost entries, where refers to the width of the wall.

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'