Brick Wall LeetCode Solution

Difficulty Level Medium
Frequently asked in Bloomberg Facebook Google OracleViews 2789

Problem Statement

Brick Wall LeetCode Solution – 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.

Brick Wall LeetCode Solution

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

Explanation

Intuition

If the goal here is to find where a line will cross the minimum bricks, then we could also say that the goal is to find where the most brick edges line up.

What are Edges?

We can consider the edges to occur at an index representing the current running total of the previous elements of a given row of the wall. For example, if the row is defined as [1,2,2,1], then the inside edges occur at [1,1+2,1+2+2], or [1,3,5].

If we now know how to find the edges, then we’re left with finding out which index has the highest frequency of edges, which naturally calls for a frequency map or HashMap in simple terms.

So we can iterate through each row in the wall, keep a running total of the current row (rowSum), and then update the frequency of each edge’s index in our frequency map (freq).

Once we’re done filling freq, we just need to iterate through it to find the highest value (best), which represents the number of edges aligned on a single index.

NOTE

Our actual answer, however, is the number of bricks, not edges, so we should return the ( total number of rows – best ).

Code

Java Code for Brick Wall

class Solution {
    int best = 0;
    Map<Integer, Integer> freq = new HashMap<>();
    public int leastBricks(List<List<Integer>> wall) {
        for (int i = 0; i < wall.size(); i++)
            processRow(wall.get(i));
        return wall.size() - best;
    }
    public void processRow(List<Integer> row) {
        int rowSum = row.get(0);
        for (int j = 1; j < row.size(); j++) {
            int f = freq.getOrDefault(rowSum, 0) + 1;
            freq.put(rowSum, f);
            if (f > best) best = f;
            rowSum += row.get(j);
        } 
    }
}

 

Python Code for Brick Wall

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        freq = defaultdict(int)
        for row in wall:
            rowSum = row[0]
            for j in range(1, len(row)):
                freq[rowSum] += 1
                rowSum += row[j]
        return len(wall) - max(freq.values() or [0])

 

C++ Code for Brick Wall

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> freq;
        int best = 0;
        for (int i = 0; i < wall.size(); i++) {
            int rowSum = wall[i][0];
            for (int j = 1; j < wall[i].size(); j++) {
                freq[rowSum]++;
                best = max(best, freq[rowSum]);
                rowSum += wall[i][j];
            };
        };
        return wall.size() - best;
    };

};

Time & Space Complexity for Brick Wall LeetCode Solution

Since we iterate through each row and every element so the Time Complexity will be: O (m x n), where

m –> Number of rows

n –> Number of elements in each row

Since we are storing edges in a Frequency map so in the worst case every brick is of 1 unit width so the map would have w keys so the space complexity is: O(W)

Translate »