Solution: Brick Wall
Tags: algorithms, javascript, java, python
Published: 2021-04-22 08:56:20

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/brick-wall/discuss/1170889).*

---

#### [Leetcode Problem #554 (*Medium*): Brick Wall](https://leetcode.com/problems/brick-wall/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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:|![Example Visual](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wj94p4p4op6o0za3pmhp.png)

---

#### ***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:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var leastBricks = function(wall) {
    let freq = new Map(), best = 0
    for (let i = 0; i < wall.length; i++) {
        let row = wall[i], rowSum = row[0]
        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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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])
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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;
    };
};
```