Greedy Solution to Reconstruct a 2-Row Binary Matrix
- Time:2020-09-10 13:27:27
- Class:Weblog
- Read:38
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] <= 2Hints:
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) —
Recommend:The PUSHD/POPD Implementation in Pure Windows Batch
Three ways to Reverse a List/Array/Tuple in Python
How to Compute the Interval List Intersections using Two Pointer
How to Summary Ranges using O(N) Two Pointer Algorithm?
Microbit Programming: How to Make a Catching-Apple Game by Using
The enumerate method in Magik Programming
Add Two Numbers by Two Linked List (most significant digit comes
The enumerate function in Javascript
How to Check If Word Is Valid After Substitutions using Stack or
5 Best Instagram Marketing Strategies for Blogs
- Comment list
-
- Comment add