C++|| O(N) Solution Step By Step
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves reconstructing a binary matrix based on the given upper and lower 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves reconstructing a binary matrix based on the given upper and lower sums and a colsum array. The idea is to allocate the \'1\'s in each column such that the sum of the rows matches the given upper and lower values while adhering to the constraints provided by colsum.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1> Initialization: Create a 2D vector v with 2 rows and columns equal to the size of colsum, initialized to 0.\n\n2> Distribute \'2\'s: If an element in colsum is 2, both rows must have a \'1\' in that column. Decrement upper and lower accordingly.\n\n3> Distribute \'1\'s: If an element in colsum is 1, place a \'1\' in the row which has remaining sum to distribute. Prefer placing \'1\' in the upper row first if it has remaining capacity.\n\n4>Validation: After placing all \'1\'s, check if upper and lower have reached 0. If not, return an empty matrix indicating it\'s not possible to form such a matrix.\n\n5>Return Result: If valid, return the constructed matrix.\n# Complexity\n- Time complexity: O(n), where \uD835\uDC5B is the size of colsum. We iterate through the colsum array twice.\n# - Space complexity: O(n), the space used to store the resulting 2D vector.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {\n        vector<vector<int>>v(2, vector<int>(colsum.size(),0));\n        for(int k = 0; k<colsum.size(); k++){\n            if(colsum[k]==2 && upper>0 && lower>0){\n                v[0][k]=1;\n                v[1][k]=1;\n                upper--;\n                lower--;\n                colsum[k]=0;\n            }\n        }\n        for(int k = 0; k<colsum.size();k++){\n            if(colsum[k]==1&&upper>0){\n                v[0][k]=1;\n                upper--;\n                colsum[k]=0;\n            }else if(colsum[k]==1&&lower>0){\n                v[1][k]=1;\n                lower--;\n                colsum[k]=0;\n            }\n        }\n        bool b = true;\n        for(int i = 0; i<colsum.size(); i++){\n            if(colsum[i]>0){\n                b = false;\n                break;\n            }\n        }\n        if(upper>0 || lower>0){\n            b=false;\n        }\n        if(b){\n            return v;\n        }else{\n            v.clear();\n            return v;\n        }\n    }\n};\n```
['C++']