Consice C++ solution using unordered_map


  • 1
    C

    The worst case scenario is that we have # of rows cuts which will basically cut every brick from each row. So we keep an unordered_set to store the possible cuts and how many time this cut has been visited by all the rows. Then # of rows + mincut (which is a minus number here) will get us the minimal cuts.

        int leastBricks(vector<vector<int>>& wall) 
        {
            if(wall.empty()) return 0;
            int row = wall.size(), width = 0, minCut = 0;
            unordered_map<int, int> cut;
            for(int i=0; i<row; i++)
            {
                int rowWidth = 0;
                for(int j=0; j<wall[i].size()-1; j++) 
                {
                    rowWidth += wall[i][j];
                    cut[rowWidth]--;
                    minCut = min(minCut, cut[rowWidth]);
                }
            }
            return row+minCut;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.