Java, counting, greedy, beats 100%, explained
We can solve this doing traversal and distribute numbers as per sum at each step. If in the end upper and lower limits are not 0s it means than solution is not 
We can solve this doing traversal and distribute numbers as per sum at each step. If in the end upper and lower limits are not 0s it means than solution is not possible.\nFor the distribution use greedy approach - because we can return any correct solution just start fill with 1-s from the upper row.\nDetailed logic:\ncount how many 2s we have. we need to reserve it and not use to early\nthe rest of upper and lower we can distribute as we like, starting from upper row (actual order doesn\'t really matter)\nwe have only 3 cases - colsum[i] is 0 - it means both numbers are 0, it\'s 1 - it means only one is 1, and 2 - this is only when both upper and lower are 1\nwhile distributing we decrement upper and lower. At each step and in the end we need to check if lower and upper are ok.\n\nO(len(colsum)) time - iterate over colsum 2 times, one to count 2s, second to form the result. O(1) space - no extra space used except for resulting lists.\n\n```\n    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {\n        List<List<Integer>> res = new ArrayList();\n        //check number of 2-s in colsum\n        int t = 0;\n        for (int n : colsum) {\n            if (n == 2 ) ++t;\n        }\n        List<Integer> up = new ArrayList(), down = new ArrayList();\n        //decrement number of 2s from upper and lower so it contribution reserved\n        upper-=t;\n        lower-=t;\n        //check every number in colsum in greedy manner starting from the upper\n        for (int n : colsum) {\n            //start from 0, it covers case when n == 0\n            int x = 0, y = 0;\n            //if sum for the col is 2 the only way to get it is to make up and low both 1\n            if (n == 2) {\n                x = y = 1;\n            } else if (n == 1) {\n                //if it\'s 1 it means only one from up/lower is 1. Start from upper always\n                if (upper > 0) {\n                    --upper;\n                    x = 1;\n                    y = 0;\n                } else {\n                    --lower;\n                    x = 0;\n                    y = 1;\n                }\n            }\n            //check if we out of limits \n            if (upper < 0 || lower < 0)\n                return res;\n            //add number to upper and lower rows\n            up.add(x); down.add(y);\n        }\n        //check if we have used exact number for each row sum\n        if (lower == 0 && upper == 0) {\n            res.add(up); res.add(down);\n        }\n        return res;\n    }\n```
['Greedy', 'Counting', 'Java']