Arrays - Brick Wall

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 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.

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2
Explanation: If we visualize the wall array, this is how it looks like. As you can see the highlighted line is passing with minimum number of bricks.

Problem 1 solution

Input: wall = [[1],[1],[1]]
Output: 3

Solution 1 - At every brick unit, count number of cuts needed from top row to bottom row (Brute force approach)
Solution 2 - Find the gaps count at brick position and find the position with maximum gaps, that means less cuts (Efficient approach)

Per the problem statement it is clear that every row will have same width though each brick width may be different. So, in this approach we are going to get the width of the row as a first step, then at every single brick unit check whether a cut is needed or not and store this data into a HashMap (One exception case is if the width of the wall is one, we simply take the height of the wall, see example 2 above).

Finally, return the minimum value stored in the HashMap. i.e. minimum number of cuts needed to go from top row to bottom row.

import java.util.HashMap; import java.util.List; import java.util.concurrent.atomic.AtomicInteger; public class BrickWall { static int bruteForceApproach(List<List<Integer>> wall) { HashMap<Integer, Integer> map = new HashMap<>(); // first get the width int width = 0; List<Integer> first_row = wall.get(0); for(int brick : first_row) { width += brick; } if(width == 1) { return wall.size(); } for(List<Integer> row: wall) { int brickUnits=1; int currentWidth =row.get(0); int i=1; while(brickUnits < width){ if(currentWidth > brickUnits) { map.merge(brickUnits, 1, Integer::sum); } else { map.merge(brickUnits, 0, Integer::sum); currentWidth += row.get(i); i++; } brickUnits++; } } // get the minimum cut point, min value from HashMap int min = Integer.MAX_VALUE; for(Integer val: map.values()) { if(val < min) { min = val; } } return min; } public static void main(String[] args) { List<List<Integer>> wall = List.of( List.of(1,2,2,1), List.of(3,1,2), List.of(1,3,2), List.of(2,4), List.of(3,1,2), List.of(1,3,1,1) ); System.out.println(bruteForceApproach(wall)); wall = List.of( List.of(1), List.of(1), List.of(1) ); System.out.println(bruteForceApproach(wall)); } }

Complexity Analysis:

Time complexity: Above code runs in O(W * H) time where W is the width of the wall and H is the height of the wall.
Space complexity: O(W), since we are storing every brick unit into HashMap

In this approach, we will count the gaps at brick position in every row and store this into a HashMap, then at the end we will find the index which had maximum number of gaps, that means lesser number of cuts needed and subtract this from wall height to get minimum cuts needed.

Implementation details:

We will first initialize a HashMap to store the brick position as key and number of gaps found as value.
Then loop through each row of wall, and store the brick position (i.e. width of current brick) as key and put 1 as value if the key doesn't exist, otherwise increment the value. When we loop through each row, we will ignore last brick, because we cannot include edge positions as per problem statement.
Now, get the maximum number of gaps found, by going through values of HashMap and get the maximum value.
Finally subtract the maximum number of gaps found from wall height, this will give minimum number of cuts needed to reach from top row to bottom row.

Let's look at an example, say if the given input wall is [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]

After going through first row [1, 2, 2, 1], gaps map will look like this.

Gaps
Position	Gaps
1	1
3	1
5	1

After going through second row [3, 1, 2], gaps map will look like this.

Gaps
Position	Gaps
1	1
3	2
4	1
5	1

After going through third row [1, 3, 2], gaps map will look like this.

Gaps
Position	Gaps
1	2
3	2
4	2
5	1

After going through fourth row [2, 4], gaps map will look like this.

Gaps
Position	Gaps
1	2
2	1
3	2
4	2
5	1

After going through fifth row [3, 1, 2], gaps map will look like this.

Gaps
Position	Gaps
1	2
2	1
3	3
4	3
5	1

After going through sixth row [1, 3, 1, 1], gaps map will look like this.

Gaps
Position	Gaps
1	3
2	1
3	3
4	4
5	2

As we can see the maximum number of gaps found are 4, we will subtract this from wall height which is 6 -4 = 2. So we need to cut a minimum of 2 bricks to reach from top row to bottom row.

import java.util.HashMap; import java.util.List; public class BrickWall { static int countGapsAndFindMaxGaps(List<List<Integer>> wall) { final HashMap<Integer, Integer> gaps = new HashMap<>(); for(List<Integer> row: wall) { int currentBrickPosition = 0; // we will be ignoring the last brick, because we cannot include edge positions per problem statement for(int i=0; i<row.size()-1; i++) { currentBrickPosition += row.get(i); gaps.merge(currentBrickPosition, 1, Integer::sum); } } int maxGaps = 0; for(Integer gap : gaps.values()) { if(gap>maxGaps) { maxGaps = gap; } } return wall.size() - maxGaps; } public static void main(String[] args) { List<List<Integer>> wall_1 = List.of( List.of(1,2,2,1), List.of(3,1,2), List.of(1,3,2), List.of(2,4), List.of(3,1,2), List.of(1,3,1,1) ); List<List<Integer>> wall_2 = List.of( List.of(1), List.of(1), List.of(1) ); System.out.println(countGapsAndFindMaxGaps(wall_1)); System.out.println(countGapsAndFindMaxGaps(wall_2)); } }

Complexity Analysis:

Time complexity: Above code runs in O(m *n) time where m is the width of row and n is the wall height.
Space complexity: O(m) since we are storing position index to gap count into a HashMap

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis:

Implementation details:

Complexity Analysis: