Greedy Solution to 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.
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^5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 2

Hints:
You cannot do anything about colsum[i] = 2 case or colsum[i] = 0 case. Then you put colsum[i] = 1 case to the upper row until upper has reached. Then put the rest into lower row.
Hide Hint 2
Fill 0 and 2 first, then fill 1 in the upper row or lower row in turn but be careful about exhausting permitted 1s in each row.

C++ Greedy Algorithm to Reconstruct the Binary Matrix

The column count is known. Thus we iterate each column. If the count is two, we know there are two 1’s in original binary matrix. If the count is zero, we know both values in the column are zero.

If it is 1, there are two possibilities. However, we can use the greedy approach – to fill 1 in the row where the row counter is larger.

At any time, if both row counts fall negative, we know there isn’t such binary matrix – return empty.

At the end, we also need to return empty matrix if any of the row counter is positive – meaning that it does not match the input.

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

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        vector<vector<int>> r(2, vector<int>(colsum.size(), -1));
        for (int i = 0; i < colsum.size(); ++ i) {
            if (colsum[i] == 2) {
                if (--upper < 0) return {};
                if (--lower < 0) return {};
                r[0][i] = 1;
                r[1][i] = 1;
            } else if (colsum[i] == 0) {
                r[0][i] = 0;
                r[1][i] = 0;
            } else {
                if (upper > lower) {
                    r[0][i] = 1;
                    r[1][i] = 0;
                    if (-- upper < 0) return {};
                } else {
                    r[0][i] = 0;
                    r[1][i] = 1;
                    if (-- lower < 0) return {};
                }
            }
        }
        return ((upper == 0) && (lower == 0)) ? r : vector<vector<int>>(0);
    }
};

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        vector<vector<int>> r(2, vector<int>(colsum.size(), -1));
        for (int i = 0; i < colsum.size(); ++ i) {
            if (colsum[i] == 2) {
                if (--upper < 0) return {};
                if (--lower < 0) return {};
                r[0][i] = 1;
                r[1][i] = 1;
            } else if (colsum[i] == 0) {
                r[0][i] = 0;
                r[1][i] = 0;
            } else {
                if (upper > lower) {
                    r[0][i] = 1;
                    r[1][i] = 0;
                    if (-- upper < 0) return {};
                } else {
                    r[0][i] = 0;
                    r[1][i] = 1;
                    if (-- lower < 0) return {};
                }
            }
        }
        return ((upper == 0) && (lower == 0)) ? r : vector<vector<int>>(0);
    }
};

The above C++ code runs at complexity O(N) where N is the number of the column. The space requirement is O(1) constant disregard the output binary matrix.

–EOF (The Ultimate Computing & Technology Blog) —