Leetcode 1253. Reconstruct a 2-Row Binary Matrix
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 andlower
(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 toupper
)- Lower row: [0,0,1] (the sum is
1
which equals tolower
)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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.