Problem Explanation

In this problem, we have a binary matrix of size 2 x n which means we have 2 rows and n columns. It's known as a binary matrix because each cell in the matrix can hold a 1 or 0.

We are given the following parameters to construct the matrix:

• Upper: which is the sum of elements in the upper row.
• Lower: which is the sum of elements in the lower row.
• Colsum : an array with n elements where each element represents the sum of elements in that column.

Our task is to construct a matrix such that the sum of elements in the upper row equals to Upper, sum of elements in the lower row equals to Lower, AND, the sum of elements in each column equals to the corresponding value in colsum.

If it's impossible construct such matrix, we return an empty array. If there are multiple possible matrices, we can return any.

Let's see an example:

Input : upper = 2, lower = 1, colsum = [1,1,1] Output: [[1,1,0],[0,0,1]]

Here, we have 3 columns and upper(sum of upper row elements) is 2 and lower(sum of lower row elements) is 1. Our goal matrix should look like this:

• Upper row: [1,1,0] (the sum is 2 which equals to upper)
• Lower row: [0,0,1] (the sum is 1 which equals to lower)

Now, if we check the colsum (sum of each column), it's also in line with the provided input: [1,1,1] which is [1+0, 1+0, 0+1]

Therefore, the matrix [[1,1,0],[0,0,1]] is a correct answer.

Problem Approach

The solution iterates through the columns of the matrix. It assigns the value of 1 to both rows if colsum has the value of 2 and decrements the upper and lower.

Then it iterates again to assign 1 to the upper row when there is remainder in colsum and upper. It repeats the same procedure for the lower row for its remainder. If the upper and lower sums become 0, it returns the answer.

Python Solution

1
2python
3from typing import List
4
5class Solution:
6    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
7        if upper + lower != sum(colsum): return [] 
8        ans = [[0]*len(colsum) for _ in range(2)]
9        for i, val in enumerate(colsum):
10            if val == 2:
11                ans[0][i] = ans[1][i] = 1
12                upper -= 1
13                lower -= 1
14        if upper < 0 or lower < 0: return [] 
15        for i, val in enumerate(colsum):
16            if val == 1:
17                if upper > 0:
18                    ans[0][i] = 1
19                    upper -= 1
20                else:
21                    ans[1][i] = 1
22                    lower -= 1
23        if upper == 0 and lower == 0:
24            return ans
25        return []

Java Solution

1
2java
3class Solution {
4    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
5        List<List<Integer>> ans = new ArrayList<>();
6        int[] upperRow = new int[colsum.length];
7        int[] lowerRow = new int[colsum.length];
8        
9        for (int i = 0; i < colsum.length; i++){
10            if (colsum[i] == 2){
11                upperRow[i] = lowerRow[i] = 1;
12                upper--;
13                lower--;
14            }    
15        }
16        
17        if (upper<0 || lower<0){
18            return ans;
19        }
20        
21        for (int i=0; i<colsum.length; ++i) {
22            if (colsum[i] == 1 && upper >0) {
23                upperRow[i] = 1;
24                upper -= 1;
25            } else if (colsum[i] == 1 && lower >0) { 
26                lowerRow[i] = 1;
27                lower -= 1;
28            }
29        }
30        
31        if (upper == 0 && lower == 0){
32            ans.add(Arrays.asList(Arrays.stream(upperRow).boxed().toArray(Integer[]::new)));
33            ans.add(Arrays.asList(Arrays.stream(lowerRow).boxed().toArray(Integer[]::new)));
34            return ans;
35        }
36        return new ArrayList<>();
37    }
38}

Javascript Solution

1
2javascript
3var reconstructMatrix = function(upper, lower, colsum) {
4    let upperRow = new Array(colsum.length).fill(0);
5    let lowerRow = new Array(colsum.length).fill(0);
6    for (let i = colsum.length - 1; i >= 0; i--){
7        if (colsum[i] == 2){
8            upperRow[i] = lowerRow[i] = 1;
9            upper--, lower--;
10        }
11    }
12    if (upper < 0 || lower < 0) return [];
13    for (let i = 0; i < colsum.length; i++){
14        if (colsum[i] == 1 && upper > 0){
15            upperRow[i] = 1;
16            upper--;
17        } else if (colsum[i] == 1){
18            lowerRow[i] = 1;
19            lower--;
20        }
21    }
22    if (upper == 0 && lower == 0) return [upperRow,lowerRow];
23    return [];
24};

C++ Solution

1
2c++
3class Solution {
4public:
5    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
6        int n = colsum.size();
7        vector<vector<int>> ans(2, vector<int>(n,0));
8        for( int i = 0 ; i < n ; i++ ) {
9            if(colsum[i]) {
10                ans[0][i] = min(1, upper);
11                ans[1][i] = colsum[i] - ans[0][i];
12                upper -= ans[0][i];
13                lower -= ans[1][i];
14            }
15        }
16        if(upper || lower)
17            return {};
18        return ans;
19    }
20};

C# Solution

1
2csharp
3public class Solution {
4    public IList<IList<int>> ReconstructMatrix(int upper, int lower, int[] colsum) {
5        List<IList<int>> result = new List<IList<int>>();
6        int[] top = new int[colsum.Length];
7        int[] bottom = new int[colsum.Length];
8        for (int i = 0; i < colsum.Length; i++)
9        {
10            if (colsum[i] == 2)
11            {
12                top[i] = 1;
13                bottom[i] = 1;
14                upper--; lower--;
15            }
16        }
17        for (int i = 0; i < colsum.Length; i++)
18        {
19            if (colsum[i] != 2)
20            {
21                if (colsum[i] == 1 && upper > 0) { top[i] = 1; upper--; }
22                if (colsum[i] == 1 && top[i] != 1) { bottom[i] = 1; lower--; }
23            }
24        }
25        if (upper != 0 || lower != 0) return result;
26        result.Add(top);
27        result.Add(bottom);
28        return result;
29    }
30}

The solution follows the approach outlined above: it constructs the top and bottom rows by handling the case of colsum equals to 2 first, and then iterates again to handle the case of colsum equals to 1. In the end it checks if both upper and lower are equal to 0, and if so, it returns the constructed matrix, otherwise it returns an empty matrix.In all of these solutions, the upper and lower parameters represent the sum of elements in the upper and lower row of the matrix respectively. The colsum parameter on the other hand, is an array where each element represents the sum of elements in that column.

The solution starts by initializing an empty 2-dimensional matrix filled with zeros. Then it iterates through the colsum array. If the element in colsum array is 2, it sets the corresponding element in both rows of the solution matrix to 1 and decrements upper and lower. If either upper or lower becomes negative, it means it's impossible to construct such matrix, so it returns an empty array.

In the next step, it iterates through the colsum array once more. If the element in colsum is 1, it assigns a 1 to the upper row of the solution matrix if there are still remaining elements to be assigned in the upper row (upper is greater than 0), and decrements upper. On the other hand, if upper is 0, it assigns a 1 to the lower row of the solution matrix and decrements lower.

Finally, it checks if both upper and lower are 0, which means all elements have been assigned correctly in the upper and lower rows of the solution matrix. If true, it returns the solution matrix. If one of them is not 0, it means it's impossible to construct such matrix and it returns an empty array.

This solution works well because it tries to distribute the elements as evenly as possible between the two rows. It first tries to assign the elements to both rows when possible (colsum[i] == 2). Then it tries to assign the remaining elements to the upper row when possible (colsum[i] == 1 && upper > 0). This strategy ensures that if it is possible to construct a matrix, it will find a solution.