Using greedy algorithm to solve the problem <1253. Reconstruct a 2-Row Binary Matrix>.
Example
1253. Reconstruct a 2-Row Binary Matrix
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.
Answers
Greedy algorithm
Greedy strategy: Thinking col = 2 at first in colsum, then arrange col = 1
var reconstructMatrix = function(upper, lower, colsum) {
let twoCnt = 0, total = 0
for (const col of colsum) {
if (col === 2) twoCnt++
total += col
}
if (upper + lower != total) return []
if (twoCnt > Math.min(upper, lower)) return []
const n = colsum.length
const ans = Array.from({length: 2}, _ => new Uint8Array(n))
upper -= twoCnt, lower -= twoCnt
for (let i = 0; i < n; i++) {
if (colsum[i] === 2) {
ans[0][i] = ans[1][i] = 1
} else if (colsum[i] === 1) {
if (upper > 0) {
ans[0][i] = 1
upper--
} else {
ans[1][i] = 1
}
}
}
return ans
};func reconstructMatrix(upper int, lower int, colsum []int) [][]int {
twoCnt, total := 0, 0
for _, col := range colsum {
if col == 2 {
twoCnt++
}
total += col
}
if upper + lower != total || twoCnt > min(upper, lower) {
return [][]int{}
}
n := len(colsum)
ans := make([][]int, 2)
ans[0], ans[1] = make([]int, n), make([]int, n)
upper, lower = upper - twoCnt, lower - twoCnt
for i, col := range colsum {
if col == 2 {
ans[0][i], ans[1][i] = 1, 1
} else if col == 1 {
if upper > 0 {
ans[0][i] = 1
upper--
} else {
ans[1][i] = 1
}
}
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}class Solution {
function reconstructMatrix($upper, $lower, $colsum) {
$twoCnt = 0;
$total = 0;
foreach ($colsum as $col) {
if ($col === 2) $twoCnt++;
$total += $col;
}
if ($upper + $lower !== $total || $twoCnt > min($upper, $lower)) return [];
$n = count($colsum);
$ans = array_fill(0, 2, array_fill(0, $n, 0));
$upper -= $twoCnt;
$lower -= $twoCnt;
foreach ($colsum as $i => $col) {
if ($col === 2) {
$ans[0][$i] = 1;
$ans[1][$i] = 1;
} elseif ($col === 1) {
if ($upper > 0) {
$ans[0][$i] = 1;
$upper--;
} else {
$ans[1][$i] = 1;
}
}
}
return $ans;
}
}class Solution {
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
int twoCnt = 0, total = 0;
for (int col : colsum) {
if (col == 2) twoCnt++;
total += col;
}
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if (upper + lower != total || twoCnt > Math.min(upper, lower)) return ans;
ans.add(new ArrayList<Integer>());
ans.add(new ArrayList<Integer>());
upper -= twoCnt;
lower -= twoCnt;
int n = colsum.length;
for (int i = 0; i < n; i++) {
if (colsum[i] == 2) {
ans.get(0).add(1);
ans.get(1).add(1);
} else if (colsum[i] == 1) {
if (upper > 0) {
ans.get(0).add(1);
ans.get(1).add(0);
upper--;
} else {
ans.get(0).add(0);
ans.get(1).add(1);
}
} else {
ans.get(0).add(0);
ans.get(1).add(0);
}
}
return ans;
}
}public class Solution {
public IList<IList<int>> ReconstructMatrix(int upper, int lower, int[] colsum) {
int twoCnt = 0, total = 0;
foreach (int col in colsum) {
if (col == 2) twoCnt++;
total += col;
}
IList<IList<int>> ans = new List<IList<int>>();
if (upper + lower != total || twoCnt > Math.Min(upper, lower)) return ans;
ans.Add(new List<int>());
ans.Add(new List<int>());
int n = colsum.Length;
upper -= twoCnt;
lower -= twoCnt;
for (int i = 0; i < n; i++) {
if (colsum[i] == 2) {
ans[0].Add(1);
ans[1].Add(1);
} else if (colsum[i] == 1) {
if (upper > 0) {
ans[0].Add(1);
ans[1].Add(0);
upper--;
} else {
ans[0].Add(0);
ans[1].Add(1);
}
} else {
ans[0].Add(0);
ans[1].Add(0);
}
}
return ans;
}
}#define MIN(a, b) (a < b ? a : b)
int** reconstructMatrix(int upper, int lower, int* colsum, int colsumSize, int* returnSize, int** returnColumnSizes){
int twoCnt = 0, total = 0;
for (int i = 0; i < colsumSize; i++) {
if (colsum[i] == 2) twoCnt++;
total += colsum[i];
}
if (upper + lower != total || twoCnt > MIN(upper, lower)) {
*returnSize = 0;
return NULL;
}
int** ans = malloc(sizeof(int*) * 2);
ans[0] = malloc(sizeof(int) * colsumSize);
ans[1] = malloc(sizeof(int) * colsumSize);
upper -= twoCnt;
lower -= twoCnt;
for (int i = 0; i < colsumSize; i++) {
if (colsum[i] == 2) {
ans[0][i] = 1;
ans[1][i] = 1;
} else if (colsum[i] == 1) {
if (upper > 0) {
ans[0][i] = 1;
ans[1][i] = 0;
upper--;
} else {
ans[0][i] = 0;
ans[1][i] = 1;
}
} else {
ans[0][i] = 0;
ans[1][i] = 0;
}
}
*returnSize = 2;
*returnColumnSizes = malloc(sizeof(int) * 2);
(*returnColumnSizes)[0] = colsumSize;
(*returnColumnSizes)[1] = colsumSize;
return ans;
}class Solution {
public:
vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
int twoCnt = 0, total = 0;
for (int col : colsum) {
if (col == 2) twoCnt++;
total += col;
}
if (upper + lower != total || twoCnt > min(upper, lower)) return {};
int n = colsum.size();
vector<vector<int>> ans(2, vector<int>(n, 0));
upper -= twoCnt;
lower -= twoCnt;
for (int i = 0; i < n; i++) {
if (colsum[i] == 2) {
ans[0][i] = 1;
ans[1][i] = 1;
} else if (colsum[i] == 1) {
if (upper > 0) {
ans[0][i] = 1;
upper--;
} else {
ans[1][i] = 1;
}
}
}
return ans;
}
};class Solution:
def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
twoCnt, total = 0, 0
for col in colsum:
if col == 2: twoCnt += 1
total += col
if upper + lower != total or twoCnt > min(upper, lower): return []
upper, lower = upper - twoCnt, lower - twoCnt
n = len(colsum)
ans = [[0] * n for _ in range(2)]
for i, col in enumerate(colsum):
if col == 2: ans[0][i], ans[1][i] = 1, 1
elif col == 1:
if upper > 0: ans[0][i], upper = 1, upper - 1
else: ans[1][i] = 1
return ans