Skip to main content

554. Brick Wall - LeetCode Solution

Problem Statement : 
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 goes 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.
Example:
Input: [[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]

Output: 2

Explanation:
 
Note:
  1. The width sum of bricks in different rows are the same and won't exceed INT_MAX.
  2. The number of bricks in each row is in the range [1,10,000]. The height of the wall is in the range [1,10,000]. The total number of bricks of the wall won't exceed 20,000.
Intuition:
  1. we will keep summing the width of each brick for every row
  2. for example for the first level = [1 3 5 6]
  3. the final sum is, of course, going to be same (width of the wall) for each row(in this case: 6)
  4. We know if we cross the edge of a brick, it is not counted
  5. Also if we are getting a sum S at some position in one row, and same sum S in the below row, this means that they both are having an edge at the same position 
  6. for example for S = 4, [1 3] and [3 1] are having an edge at same point => it will be profitable to cross the wall along the path where max no of rows are having an edge at the same common point
  7. In other words, we  should form the line along the path where we have the most common prefix sum
  8. we will count the number of rows with the most common prefix sum and subtract this number from the size of the wall to get the final answer.
C++ CODE:
class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        map<int,int> m;
        for(auto v : wall){
            int sum = 0;
            for(int i=0;i<v.size()-1;i++){
                sum += v[i];
                m[sum]++;
            }
        }
        int mc=0;
        for(auto it : m){
            if(mc < it.second)
                mc = it.second;
        }
        return wall.size() - mc;
    }
};
NOTE : 
In order to speedify your solution on any platform you can add this peice of code above the class Solution
static int accel = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();


Comments

Post a Comment

Popular posts from this blog

All About Flutter

F L U T T E R What is Flutter? Flutter is an open-source mobile SDK developer can use to build native-looking Android and iOS applications from the same code base. Flutter has been around since 2015 when Google introduced it and remained in the beta stage before its official launch in December 2018. Since then, the buzz around Flutter has been growing stronger. Widgets The central idea behind Flutter is the use of widgets. It’s by combining different widgets that developers can build the entire UI. Each of these widgets defines a structural element (like a button or menu), a stylistic element (a font or color scheme), a layout aspect (like padding), and many others. Flutter also provides developers with reactive-style views. To avoid performance issues deriving from using a compiled programming language to serve as the JavaScript bridge, Flutter uses Dart. It compiles Dart   ahead of time (AOT)   into the native code for multiple platforms. Flutter also provides developers wit...
Post a Comment
Read more

Are you smart?

S ocrates once said " I know one thing, that I know nothing " Hello humans, Put on a helmet, because after reading this your mind may explode 😨 (just kidding). I will be sharing with you some famous paradoxes that will hit your brain hard. Let's begin  1. Do you have a brother?   Consider a family, where there is a mother, father, and two children. One of the children is a boy, then what are the chances of the second one being a girl. Is it 1/2, because the other children can be either a boy or a girl. But, wait a minute...   There are four possible combinations of two children ( Boy, Boy), (Boy, Girl),(Girl, Boy) and (Girl, Girl). Since one of the children is a boy, so the combination can not be (Girl, Girl), this means we are left with 3 possible combinations. This gives us the chances of the other children being a boy as 1/3. Uhhh... this is confusing is it 1/2 or 1/3. You tell me🤪 2. Crocodility Once upon a time, a mother and a son visited a zoo. Accidentally, the ...
Post a Comment
Read more

699. Falling Squares - LeetCode Solution

699 .   Falling Squares On an infinite number line (x-axis), we drop given squares in the order they are given. The   i -th square dropped ( positions[i] = (left, side_length) ) is a square with the left-most point being   positions[i][0]   and sidelength   positions[i][1] . The square is dropped with the bottom edge parallel to the number line, and from a higher height than all currently landed squares. We wait for each square to stick before dropping the next. The squares are infinitely sticky on their bottom edge, and will remain fixed to any positive length surface they touch (either the number line or another square). Squares dropped adjacent to each other will not stick together prematurely.   Return a list   ans   of heights. Each height   ans[i]   represents the current highest height of any square we have dropped, after dropping squares represented by   positions[0], positions[1], ..., positions[i] . Example 1: Input: [[1,...
Post a Comment
Read more