🔥Beats 93.72%🔥✅Easiest (C++/Java/Python) Solution With Detailed Explanation✅
Intuition\nThe intuition for reconstructing a 2D matrix involves first checking if the total upper and lower row sums match the required column sums, then alloc
# Intuition\nThe intuition for reconstructing a 2D matrix involves first checking if the total upper and lower row sums match the required column sums, then allocating 1s to each row based on column sum values, prioritizing columns with a sum of 2, followed by distributing the remaining 1s between the two rows while respecting the upper and lower limits.\n\n\n![Screenshot 2024-02-14 084843.png](https://assets.leetcode.com/users/images/6f8d9ff3-8fcd-406f-afb9-f41bb75224a7_1707880941.5600483.png)\n\n# Approach\n\n1. **Initialization**: The code initializes variables to keep track of the number of columns that should have a sum of 1 and 2, based on the `colsum` array. It also calculates the initial sums for the upper and lower rows after accommodating columns with a sum of 2.\n\n2. **Feasibility Check**: Before attempting to construct the matrix, the code checks if the desired configuration is possible by comparing the total sum of `upper` and `lower` with the total sum required by `colsum`. If the total sum doesn\'t match, or if the adjusted sums for upper or lower rows (after accounting for columns with a sum of 2) are negative, the function immediately returns an empty matrix, indicating that reconstruction is not possible.\n\n3. **Matrix Construction**: The algorithm then proceeds to construct the matrix row by row, column by column. For columns with a `colsum` of 2, it places a 1 in both the upper and lower rows. For columns with a `colsum` of 1, it prefers to place a 1 in the upper row until the upper sum is fully allocated, after which any remaining columns with a `colsum` of 1 are allocated to the lower row. This step continues until all columns are processed.\n\n4. **Result**: If the algorithm can successfully allocate the sums according to the `colsum` while respecting the `upper` and `lower` constraints, it returns the constructed matrix. Otherwise, it has already returned an empty matrix in the feasibility check step.\n\n\n# Complexity\n1. **Time Complexity**: The overall time complexity is \\(O(n)\\), where \\(n\\) is the length of the `colsum` array. This is because the algorithm iterates through the `colsum` array exactly once to construct the matrix, and the initial counting of 1s and 2s in `colsum` also requires a single pass through the array.\n\n2. **Space Complexity**: The space complexity is \\(O(n)\\) due to the storage requirements of the resulting 2D matrix, which has 2 rows and `n` columns. The rest of the variables used for counting and tracking the sum allocations are of constant space, not dependent on the input size.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> reconstructMatrix(int upper, int lower,\n                                          vector<int>& colsum) {\n        int n = colsum.size();\n\n        int count1 = 0;\n        int count2 = 0;\n\n        for (int i = 0; i < n; i++) {\n            if (colsum[i] == 1)\n                count1++;\n\n            if (colsum[i] == 2)\n                count2 += 2;\n        }\n\n        if (((upper + lower) - (count1 + count2)) != 0)\n            return {};\n\n        int upp = upper-(count2/2);\n        int low = lower-(count2/2);\n\n        if (upp < 0 || low < 0)\n            return {};\n\n        vector<vector<int>> res(2, vector<int>(n, 0));\n\n        for (int i = 0; i < n; i++) {\n            if (colsum[i] == 2) {\n                res[0][i] = 1;\n                res[1][i] = 1;\n            }\n            else if (colsum[i] == 1 && upp) {\n                res[0][i] = 1;\n                upp--;\n            }\n            else if (colsum[i] == 1 && low)\n            {\n                res[1][i] = 1;\n                low--;\n            }\n        }\n\n        return res;\n    }\n};\n```\n```Java []\nimport java.util.ArrayList;\nimport java.util.Arrays;\nimport java.util.List;\n\npublic class Solution {\n    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {\n        int n = colsum.length;\n        int count1 = 0;\n        int count2 = 0;\n\n        for (int i = 0; i < n; i++) {\n            if (colsum[i] == 1) count1++;\n            if (colsum[i] == 2) count2 += 2;\n        }\n\n        if ((upper + lower) - (count1 + count2) != 0) return new ArrayList<>();\n\n        int upp = upper - count2 / 2;\n        int low = lower - count2 / 2;\n\n        if (upp < 0 || low < 0) return new ArrayList<>();\n\n        List<List<Integer>> res = new ArrayList<>();\n        res.add(new ArrayList<>());\n        res.add(new ArrayList<>());\n\n        for (int i = 0; i < n; i++) {\n            if (colsum[i] == 2) {\n                res.get(0).add(1);\n                res.get(1).add(1);\n            } else if (colsum[i] == 1) {\n                if (upp > 0) {\n                    res.get(0).add(1);\n                    res.get(1).add(0);\n                    upp--;\n                } else {\n                    res.get(0).add(0);\n                    res.get(1).add(1);\n                    low--;\n                }\n            } else {\n                res.get(0).add(0);\n                res.get(1).add(0);\n            }\n        }\n\n        return res;\n    }\n}\n\n```\n```Python []\nfrom typing import List\n\nclass Solution:\n    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n        n = len(colsum)\n        \n        # Check if the total sum matches the desired row sums\n        if upper + lower != sum(colsum):\n            return []\n        \n        # Initialize the result matrix\n        res = [[0 for _ in range(n)] for _ in range(2)]\n        \n        for i in range(n):\n            # If colsum[i] is 2, both rows must have a 1 in the i-th column\n            if colsum[i] == 2:\n                if upper > 0 and lower > 0:\n                    res[0][i], res[1][i] = 1, 1\n                    upper -= 1\n                    lower -= 1\n                else:\n                    return []  # Not enough sums to distribute\n            # If colsum[i] is 1, distribute it to either row according to the remaining sums\n            elif colsum[i] == 1:\n                if upper > lower:\n                    res[0][i] = 1\n                    upper -= 1\n                elif lower >= upper:\n                    res[1][i] = 1\n                    lower -= 1\n                else:\n                    return []  # Not a valid scenario\n        \n        # Check if we correctly distributed all sums\n        if upper == 0 and lower == 0:\n            return res\n        else:\n            return []  # Sums were not correctly distributed\n\n```
['Greedy', 'Matrix', 'C++', 'Java', 'Python3']