Leetcode 1253: Reconstruct a 2-Row Binary Matrix
You are given a binary matrix with 2 rows and n columns, where each element is either 0 or 1. The sum of elements in the 0-th (upper) row is given by upper, the sum of elements in the 1-st (lower) row is given by lower, and the column-wise sum is given by colsum. Your task is to reconstruct the matrix based on these sums. If reconstruction is not possible, return an empty matrix.
Problem
Approach
Steps
Complexity
Input: The input consists of three integers: upper, lower, and a list colsum representing the column-wise sums.
Example: upper = 2, lower = 1, colsum = [1,1,1]
Constraints:
• 1 <= colsum.length <= 10^5
• 0 <= upper, lower <= colsum.length
• 0 <= colsum[i] <= 2
Output: Return the reconstructed matrix if valid; otherwise, return an empty matrix.
Example: [[1, 1, 0], [0, 0, 1]]
Constraints:
• The reconstructed matrix must satisfy the row and column sums.
• If no valid solution exists, return an empty matrix.
Goal: Reconstruct a valid binary matrix by ensuring that row and column sums match the given constraints.
Steps:
• Iterate through the colsum array to reconstruct the matrix by assigning values to the two rows based on the constraints.
• Ensure that the values assigned to the rows satisfy the given upper and lower row sums as well as the colsum constraints.
Goal: The constraints specify that the size of the colsum array can be up to 100,000, and the values for upper and lower are non-negative and bounded by the length of the colsum array.
Steps:
• 1 <= colsum.length <= 10^5
• 0 <= upper, lower <= colsum.length
• 0 <= colsum[i] <= 2
Assumptions:
• The input values are valid and the row sums upper and lower are feasible with respect to colsum.
• Input: upper = 2, lower = 1, colsum = [1, 1, 1]
• Explanation: The matrix is valid as the sums of the rows and columns match the given values.
• Input: upper = 2, lower = 3, colsum = [2, 2, 1, 1]
• Explanation: It is impossible to reconstruct a valid matrix, as the lower row sum exceeds the total sum of the columns.
• Input: upper = 5, lower = 5, colsum = [2, 1, 2, 0, 1, 0, 1, 2, 0, 1]
• Explanation: The matrix is reconstructed correctly, with the row and column sums matching the given values.
Approach: To solve the problem, we iterate through the column sums and try to allocate values to the two rows, ensuring that the row and column sums match the given constraints.
Observations:
• The binary matrix reconstruction requires careful allocation of values to the rows based on the column sums.
• The problem can be solved by iterating over the colsum array and using a greedy approach to assign 1s to the upper and lower rows, ensuring that the row sums are satisfied.
Steps:
• Start with two empty rows of length n.
• Iterate over the column sums. For each column, decide how to distribute the sum between the two rows, ensuring the row sums are not exceeded.
• If the solution is valid and both row sums are satisfied, return the matrix. Otherwise, return an empty matrix.
Empty Inputs:
• If colsum is an empty array, return an empty matrix.
Large Inputs:
• The solution should handle large inputs efficiently, with a maximum length of 100,000 for colsum.
Special Values:
• If the column sums are all zeros, the matrix should be filled with zeros.
Constraints:
• Ensure the solution handles all edge cases, including invalid cases where no solution exists.
vector<vector<int>> reconstructMatrix(int u, int l, vector<int>& cs) {
vector<vector<int>> res(2, vector<int>(cs.size()));
for(int i = 0; i < cs.size(); u -= res[0][i], l -= res[1][i], i++) {
res[0][i] = cs[i] == 2 || (cs[i] == 1 && l < u);
res[1][i] = cs[i] == 2 || (cs[i] == 1 && !res[0][i]);
}
return u == 0 && l == 0 ? res : vector<vector<int>>();
}
1 : Function Definition
vector<vector<int>> reconstructMatrix(int u, int l, vector<int>& cs) {
The function `reconstructMatrix` is defined, which takes two integers `u` (the number of ones in the upper row) and `l` (the number of ones in the lower row) as inputs, along with a vector `cs` containing constraints for each column.
2 : Variable Initialization
vector<vector<int>> res(2, vector<int>(cs.size()));
A 2D vector `res` of size 2xN (where N is the size of `cs`) is initialized to store the reconstructed binary matrix. The first row represents the upper row, and the second represents the lower row.
3 : For Loop
for(int i = 0; i < cs.size(); u -= res[0][i], l -= res[1][i], i++) {
A `for` loop is used to iterate over each column in the matrix. During each iteration, `u` and `l` are reduced based on the number of ones placed in the upper and lower rows respectively.
4 : Condition for Upper Row
res[0][i] = cs[i] == 2 || (cs[i] == 1 && l < u);
For the current column, if the value in `cs[i]` is 2, the upper row at `i` is set to 1. If the value in `cs[i]` is 1, the upper row is set to 1 only if the remaining number of ones in the lower row (`l`) is less than the upper row (`u`).
5 : Condition for Lower Row
res[1][i] = cs[i] == 2 || (cs[i] == 1 && !res[0][i]);
For the current column, if `cs[i]` is 2, the lower row at `i` is set to 1. If `cs[i]` is 1, the lower row is set to 1 only if the upper row at the same column is 0.
6 : Return Result
return u == 0 && l == 0 ? res : vector<vector<int>>();
After processing all columns, the function checks if both `u` and `l` have been reduced to 0, meaning the number of ones for both rows is fully satisfied. If true, it returns the reconstructed matrix `res`; otherwise, it returns an empty 2D vector indicating that the reconstruction was not possible.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The solution iterates through the colsum array once, resulting in a time complexity of O(n).
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage of the result matrix.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus