## DEV Community is a community of 891,295 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Solution: Brick Wall

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

#### Examples:

Example:
Input: [[1,2,2,1], [3,1,2], [1,3,2], [2,4], [3,1,2], [1,3,1,1]]
Output: 2
Visual: #### Constraints:

• The width sum of bricks in different rows are the same and won't exceed `INT_MAX`.
• 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`.

#### Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

If the goal here is to find where a line will cross the fewest bricks, then we could also say that the goal is to find where the most brick edges line up. 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.

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. Our actual answer, however, is the number of bricks, not edges, so we should return the total number of rows minus best.

#### Implementation:

For Javascript, it's more performant to iterate through the finished freq looking for the best result

In Python it's easier to run max() directly on freq.

For Java and C++ it's faster to keep track of best as we add values to freq.

For Java, it's also weirdly more performant to extract the row processing to a helper function.

#### Javascript Code:

``````var leastBricks = function(wall) {
let freq = new Map(), best = 0
for (let i = 0; i < wall.length; i++) {
let row = wall[i], rowSum = row
for (let j = 1; j < row.length; j++) {
freq.set(rowSum, (freq.get(rowSum) || 0) + 1)
rowSum += row[j]
}
}
for (let [k,v] of freq)
if (v > best) best = v
return wall.length - best
};
``````

#### Python Code:

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

#### Java Code:

``````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);
}
}
}
``````

#### C++ Code:

``````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];
for (int j = 1; j < wall[i].size(); j++) {
freq[rowSum]++;
best = max(best, freq[rowSum]);
rowSum += wall[i][j];
};
};
return wall.size() - best;
};
};
``````