[Java] Greedy O(n) Solution
\nclass Solution {\n    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {\n        int sum = 0, count2 = 0;\n        for (int c
```\nclass Solution {\n    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {\n        int sum = 0, count2 = 0;\n        for (int cs : colsum) {\n            sum += cs;\n            count2 += cs/2;\n        }\n        \n        if (upper + lower != sum || upper < count2 || lower < count2) return new ArrayList();\n        \n        List<List<Integer>> matrix = new ArrayList();\n        matrix.add(new ArrayList());\n        matrix.add(new ArrayList());\n        \n        for (int i = 0; i < colsum.length; i++) {\n            if (colsum[i] == 2) {\n                matrix.get(0).add(1);\n                matrix.get(1).add(1);\n            } else if (colsum[i] == 1) {\n                matrix.get(0).add(upper > lower ? 1 : 0);\n                matrix.get(1).add(upper > lower ? 0 : 1);\n            } else {\n                matrix.get(0).add(0);\n                matrix.get(1).add(0);\n            }\n            upper -= matrix.get(0).get(i);\n            lower -= matrix.get(1).get(i);\n        }\n        return matrix;\n    }\n}\n```
['Greedy']