C++ Simple Explanation
This problem can be solved using a greedy approach. We can iterate through each column and determine how we assign values to the upper cell and lower cell based
This problem can be solved using a greedy approach. We can iterate through each column and determine how we assign values to the upper cell and lower cell based on `colsum[i]`.\n\nWe can break down the greedy decision into 3 cases:\n\n1. `colsum[i]==0`\nWe don\'t do anything in this case, clearly both upper and lower cells are 0.\n\n2. `colsum[i]==2`\nWe set both upper and lower cells to 1 and decrement both upper and lower.\n\n3. `colsum[i]==1`\nEither the upper or lower cell is a 1. We make the choice based on whichever is larger - upper or lower. The intuition behind assigning the 1 to the larger quantity is to balance them out in anticipation for Case 2. Think about it this way: we only benefit by assigning in this manner. Suppose after we make this choice we only encounter Case 1 and 3, then it wouldn\'t matter the way we assigned the 1. However, if we instead encounter many instances of Case 2, we could end up having an invalid solution if upper and lower aren\'t balanced, as we\'d be decrementing both of them at the same time.\n\nHere\'s a sample input. Try going through it by not balancing upper and lower vs. balancing upper and lower. You can imagine not balancing as always assigning to upper until upper = 0, then assigning to lower. \n```\n5\n5\n[2,1,2,0,1,0,1,2,0,1]\n```\n\nAfter iterating through each column, we have to validate that both upper and lower are exactly 0. It\'s most convenient to perform this check outside the loop as if we\'d put this check inside the loop, we could only check the case where either upper or lower is less than 0.\n\nC++ code:\n```\nclass Solution {\npublic:\n    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {\n        vector<vector<int>> ans(2, vector<int>(colsum.size()));\n        for (int i=0; i<colsum.size(); ++i) {\n            if (colsum[i]==2) {\n                ans[0][i]=1;\n                ans[1][i]=1;\n                --upper;\n                --lower;\n            }\n            else if (colsum[i]==1) {\n                if (upper>lower) {\n                    ans[0][i]=1;\n                    --upper;\n                }\n                else {\n                    ans[1][i]=1;\n                    --lower;\n                }\n            }\n        }\n        if (upper!=0 || lower!=0) return {};\n        return ans;\n    }\n};\n```\n\nTime complexity: O(n)\nSpace complexity: O(n)
['Greedy', 'C']