O(n) time Java Solution Easy to understand with Comments and Explaination
We count the number of columns for which we need 1 in both rows(colsum[i] == 2), similarly we count the number of columns for which we need column-sum as 1 and 
We count the number of columns for which we need 1 in both rows(colsum[i] == 2), similarly we count the number of columns for which we need column-sum as 1 and column-sum as 0.\n\n\nFor the columns where we need the column-sum as 2, we definitely know that we need 1 in both the rows, similarly if the column-sum is 0 we know we need to place 0s in both the rows.\n\n\nFor the case where we need column-sum as 1, we need to see if we can have a 1 in row1 or do we have to have a 1 in row2. \nFor those cases I have done a precomputation and followed a somewhat greedy approach.\nThe number of columns where we need a 1 in row1 and 0 in row2 is say count1 (as mentioned in code). \nWe start assigning values to the two rows now by iterating over each value in the colsum array. If we encounter a colsum[i] == 2 or colsum[i] == 0, we assign 1s to both the rows and 0s to both the rows respectively.\n**For the cases where colsum[i] == 1, we check value of count1 variable which will tell us if we can assign a 1 to row1 or not. If value of count1 > 0, we can assign 1 to row1 and 0 to row2 and we simultaneously decrement count1. Else if count1 == 0, we assign a 0 to row1 and 1 to row2.**\n\n```\nclass Solution {\n    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {\n        \n        int n = colsum.length;\n        int sum0 = 0; // no. of columns with colsum 0\n        int sum1 = 0; // no. of columns with colsum 1\n        int sum2 = 0; // no. of columns with colsum 2\n        \n        for(int i = 0; i < n; i++){\n            if(colsum[i] == 0) sum0 ++;\n            else if(colsum[i] == 1) sum1 ++;\n            else sum2 ++;\n        }\n        \n        int count1 = upper - sum2; // no. of columns with 1 in 1st row and 0 in 2nd row\n        int count2 = lower - sum2; // no. of columns with 0 in 1st row and 1 in 2nd row\n        \n        // check if arrangement is possible or not\n        if(count1 < 0 || count2 < 0 || count1 + count2 != sum1) return new ArrayList<>();\n        \n        List<List<Integer>> ans = new ArrayList<>();\n        for(int i = 0; i < 2; i++) ans.add(new ArrayList<>());\n        \n        for(int i = 0; i < n; i++){\n            if(colsum[i] == 2){\n                ans.get(0).add(1);\n                ans.get(1).add(1);\n            }\n            else if(colsum[i] == 0){\n                ans.get(0).add(0);\n                ans.get(1).add(0);\n            }\n            else{\n                if(count1 > 0){\n                    count1 --;\n                    ans.get(0).add(1);\n                    ans.get(1).add(0);\n                }\n                else{\n                    ans.get(0).add(0);\n                    ans.get(1).add(1);\n                }\n            }\n        }\n        \n        return ans;\n    }\n}
['Greedy']