Brick Wall

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.

  Note: 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