Consice C++ solution using unordered_map

  • 1

    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];
                    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.