Description#
Given the following details of a matrix with n columns and 2 rows :
- The matrix is a binary matrix, which means each element in the matrix can be
0 or 1. - The sum of elements of the 0-th(upper) row is given as
upper. - The sum of elements of the 1-st(lower) row is given as
lower. - The sum of elements in the i-th column(0-indexed) is
colsum[i], where colsum is given as an integer array with length n.
Your task is to reconstruct the matrix with upper, lower and colsum.
Return it as a 2-D integer array.
If there are more than one valid solution, any of them will be accepted.
If no valid solution exists, return an empty 2-D array.
Example 1:
Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.
Example 2:
Input: upper = 2, lower = 3, colsum = [2,2,1,1]
Output: []
Example 3:
Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]
Constraints:
1 <= colsum.length <= 10^50 <= upper, lower <= colsum.length0 <= colsum[i] <= 2
Solutions#
Solution 1: Greedy#
First, we create an answer array $ans$, where $ans[0]$ and $ans[1]$ represent the first and second rows of the matrix, respectively.
Next, we traverse the array $colsum$ from left to right. For the current element $colsum[j]$, we have the following cases:
- If $colsum[j] = 2$, then we set both $ans[0][j]$ and $ans[1][j]$ to $1$. In this case, both $upper$ and $lower$ are reduced by $1$.
- If $colsum[j] = 1$, then we set either $ans[0][j]$ or $ans[1][j]$ to $1$. If $upper \gt lower$, then we prefer to set $ans[0][j]$ to $1$; otherwise, we prefer to set $ans[1][j]$ to $1$. In this case, either $upper$ or $lower$ is reduced by $1$.
- If $colsum[j] = 0$, then we set both $ans[0][j]$ and $ans[1][j]$ to $0$.
- If $upper \lt 0$ or $lower \lt 0$, then it is impossible to construct a matrix that meets the requirements, and we return an empty array.
At the end of the traversal, if both $upper$ and $lower$ are $0$, then we return $ans$; otherwise, we return an empty array.
The time complexity is $O(n)$, where $n$ is the length of the array $colsum$. Ignoring the space consumption of the answer array, the space complexity is $O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def reconstructMatrix(
self, upper: int, lower: int, colsum: List[int]
) -> List[List[int]]:
n = len(colsum)
ans = [[0] * n for _ in range(2)]
for j, v in enumerate(colsum):
if v == 2:
ans[0][j] = ans[1][j] = 1
upper, lower = upper - 1, lower - 1
if v == 1:
if upper > lower:
upper -= 1
ans[0][j] = 1
else:
lower -= 1
ans[1][j] = 1
if upper < 0 or lower < 0:
return []
return ans if lower == upper == 0 else []
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
int n = colsum.length;
List<Integer> first = new ArrayList<>();
List<Integer> second = new ArrayList<>();
for (int j = 0; j < n; ++j) {
int a = 0, b = 0;
if (colsum[j] == 2) {
a = b = 1;
upper--;
lower--;
} else if (colsum[j] == 1) {
if (upper > lower) {
upper--;
a = 1;
} else {
lower--;
b = 1;
}
}
if (upper < 0 || lower < 0) {
break;
}
first.add(a);
second.add(b);
}
return upper == 0 && lower == 0 ? List.of(first, second) : List.of();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
int n = colsum.size();
vector<vector<int>> ans(2, vector<int>(n));
for (int j = 0; j < n; ++j) {
if (colsum[j] == 2) {
ans[0][j] = ans[1][j] = 1;
upper--;
lower--;
}
if (colsum[j] == 1) {
if (upper > lower) {
upper--;
ans[0][j] = 1;
} else {
lower--;
ans[1][j] = 1;
}
}
if (upper < 0 || lower < 0) {
break;
}
}
return upper || lower ? vector<vector<int>>() : ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| func reconstructMatrix(upper int, lower int, colsum []int) [][]int {
n := len(colsum)
ans := make([][]int, 2)
for i := range ans {
ans[i] = make([]int, n)
}
for j, v := range colsum {
if v == 2 {
ans[0][j], ans[1][j] = 1, 1
upper--
lower--
}
if v == 1 {
if upper > lower {
upper--
ans[0][j] = 1
} else {
lower--
ans[1][j] = 1
}
}
if upper < 0 || lower < 0 {
break
}
}
if upper != 0 || lower != 0 {
return [][]int{}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| function reconstructMatrix(upper: number, lower: number, colsum: number[]): number[][] {
const n = colsum.length;
const ans: number[][] = Array(2)
.fill(0)
.map(() => Array(n).fill(0));
for (let j = 0; j < n; ++j) {
if (colsum[j] === 2) {
ans[0][j] = ans[1][j] = 1;
upper--;
lower--;
} else if (colsum[j] === 1) {
if (upper > lower) {
ans[0][j] = 1;
upper--;
} else {
ans[1][j] = 1;
lower--;
}
}
if (upper < 0 || lower < 0) {
break;
}
}
return upper || lower ? [] : ans;
}
|
