Python / C++: One Pass Greedy with Detailed Explanation
We use the greedy approach to solve this problem. We campare the sum of upper row and lower row in each iteration, and use the bigger one to reconstruct the mat
We use the greedy approach to solve this problem. We campare the sum of upper row and lower row in each iteration, and use the bigger one to reconstruct the matrix. After the for loop, we check whether the upper and lower row are 0. If it is, it means that the matrix is successful reconstructed. \n\nFor example  1:\n\nupper = 5, \nlower = 5,\ncolsum = [2,1,2,0,1,0,1,2,0,1]\n\nbeacuse firsr element is 2, both have to add 1\nupperM=[1,\nlowerM =[1,\nupper->4\nlower->4\n\n2nd element is 1 and upper=>lower, we choose upper to add 1  \nupperM=[1,1\nlowerM=[1,0\nupper->3\nlower->4\n\n3nd element is 2,both have to add 1\nupperM=[1,1,1\nlowerM=[1,0.1\nupper->2\nlower->3\n\n4th element is 0, do nothing\nupperM=[1,1,1,0\nlowerM=[1,0.1,0\n\n5th element is 1 and upper<lower, we choose lower to add 1  \nupperM=[1,1,1,0,0\nlowerM=[1,0.1,0,1\nupper->2\nlower->2\n.\n..\n...and so on\n\n\nAfter all reconstruction is completed,we check whether both upper and lower are 0 (perfectly used) or remained positive (hadn\'t been used) or negative (over used).\nIf it both are 0 return the result, if it is not return empty list.\n\nBecause it is one pass, the time complexity is O(n).\nI create an array which length is n to store all the result, so the space is O(n).\n\n\nC++\n```\nclass Solution {\npublic:\n    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {\n    vector<vector<int>> res(2,vector<int>(colsum.size(),0));\n    for(int i=0;i<colsum.size();i++){\n        \n        if(colsum[i]==2){      \n            upper--;\n            lower--;\n            res[0][i]=1;\n            res[1][i]=1;\n        }\n        else if(colsum[i]==1){\n            \n            if(upper<=lower){\n                    lower--;\n                    res[1][i]=1;\n            }\n            \n            else{       \n                    upper--;\n                    res[0][i]=1;\n            }\n\n          }\n        \n        }\n        \n    return (upper==0 && lower==0) ? res:vector<vector<int>> {};\n    }\n};\n```\n\nPython\n```\nclass Solution:\n    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n        res = [[0]*len(colsum) for _ in range(2)]\n        for i in range(len(colsum)):\n            if colsum[i]==2:\n                upper-=1\n                lower-=1\n                res[0][i]=1\n                res[1][i]=1\n            elif colsum[i]==1:\n                if upper<=lower:\n                    lower-=1\n                    res[1][i]=1\n                else:\n                    upper-=1\n                    res[0][i]=1\n        return res if upper==lower==0 else []\n```
[]