In front of you is a square brick wall made of many rows of bricks. The bricks are the same height but different width. Now you're going to draw a vertical line from the top down through the least bricks.

Brick walls are represented by a list of rows. Each row is a list of integers representing the width of each brick from left to right.

If you draw a line that just passes through the edge of a brick, it doesn't count as passing through the brick. You need to figure out how to draw to minimize the number of bricks that this line passes through and return the number of bricks that pass through.

You can't draw a line along one of the two vertical edges of the wall, which obviously doesn't go through a brick.

 

Example:

Input: [[1,2,2,1],
      [3,1,2],
      [1,3,2],
      [2,4],
      [3,1,2],
      [1,3,1,1]]

Output: 2

Interpretation: 

 

Tips:

The sum of the width of each row of bricks shall be equal and shall not exceed int'u max.

The number of bricks in each row is in the range of [1,10000], the height of the wall is in the range of [1,10000], and the total number of bricks is not more than 20000.

C++

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) 
    {
        int m=wall.size();
        unordered_map<int,int> tmp;
        for(int i=0;i<m;i++)
        {
            int sum=0;
            int n=wall[i].size();
            for(int j=0;j<n-1;j++)
            {
                sum+=wall[i][j];
                tmp[sum]++;
            }
        }
        int cc=0;
        unordered_map<int,int>::iterator it;
        for(it=tmp.begin();it!=tmp.end();it++)
        {
            cc=max(cc,it->second);
        }  
        return m-cc;  
    }
};

python

class Solution:
    def leastBricks(self, wall):
        """
        :type wall: List[List[int]]
        :rtype: int
        """
        m=len(wall)
        dic={}
        for i in range(m):
            su=0
            for j in range(0,len(wall[i])-1):
                su+=wall[i][j]
                if su not in dic:
                    dic[su]=1
                else:
                    dic[su]+=1
        cc=0
        for key in dic:
            if dic[key]>cc:
                cc=dic[key]
        return m-cc