Leetcode 1605: Find Valid Matrix Given Row and Column Sums

Input: You are provided with two arrays, rowSum and colSum, where rowSum[i] is the sum of the i-th row of a matrix and colSum[j] is the sum of the j-th column. The dimensions of the matrix are rowSum.length x colSum.length.

Example: rowSum = [5, 7], colSum = [7, 5]

Constraints:

• 1 <= rowSum.length, colSum.length <= 500

• 0 <= rowSum[i], colSum[i] <= 10^8

• sum(rowSum) == sum(colSum)

Output: Return a 2D matrix where the sum of the elements in each row equals the corresponding value in rowSum, and the sum of the elements in each column equals the corresponding value in colSum.

Example: For rowSum = [5, 7], colSum = [7, 5], one possible output could be [[0,5], [7, 0]]

Constraints:

• The matrix must be filled with non-negative integers.

Goal: To construct a matrix that satisfies both row and column sum constraints.

Steps:

• Start by initializing a 2D matrix of size rowSum.length x colSum.length, filled with zeros.

• Iterate over each element in the matrix, choosing the minimum of the remaining row sum and column sum at that position.

• Reduce the corresponding row sum and column sum by the value chosen for the matrix element.

• Repeat this process until all row and column sums are satisfied.

Goal: Given the constraints of rowSum and colSum, it is guaranteed that a valid matrix can be formed.

Steps:

• Ensure that the row sums and column sums are non-negative and satisfy the total sum equality condition.

Assumptions:

• The sum of elements in rowSum will always equal the sum of elements in colSum.

• Input: Input: rowSum = [3,8], colSum = [4,7]

• Explanation: In this case, the matrix should be such that the sum of the first row is 3 and the second row is 8. Similarly, the sum of the first column is 4 and the second column is 7. One possible solution is [[3, 0], [1, 7]].

• Input: Input: rowSum = [5,7,10], colSum = [8,6,8]

• Explanation: For this case, the matrix should be constructed such that each row sum is satisfied and each column sum is also satisfied. One possible solution is [[0,5,0], [6,1,0], [2,0,8]].

Approach: This approach leverages a greedy method where we fill the matrix by choosing the minimum value between the remaining row sum and column sum at each position. This ensures that we can satisfy the constraints while maintaining non-negative integer values in the matrix.

Observations:

• The total sum of rowSum must equal the total sum of colSum, ensuring that a solution is always possible.

• The solution requires filling each cell with the minimum value between the corresponding row and column sums, which guarantees that both constraints are met.

Steps:

• Initialize the result matrix with zeros.

• Iterate through the matrix, and for each position, place the minimum of the remaining row and column sum.

• Update the row and column sums after each placement.

• Return the matrix once all sums are satisfied.

Empty Inputs:

• Ensure that the input arrays are non-empty as per the problem constraints.

Large Inputs:

• The solution should handle large inputs efficiently, given the constraints on rowSum and colSum.

Special Values:

• Consider cases where rowSum or colSum elements are zero, ensuring the matrix remains valid.

Constraints:

• Ensure that the sum of rowSum equals the sum of colSum to guarantee that a valid matrix exists.

vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
    int m = rowSum.size(), n = colSum.size();
    vector<vector<int>> ans(m, vector<int>(n, 0));
    for(int i = 0; i < m ;i++)
    for(int j = 0; j < n; j++) {
        ans[i][j] = min(rowSum[i], colSum[j]);
        rowSum[i]-= ans[i][j];
        colSum[j]-= ans[i][j];
    }
    return ans;
}

1 : Function Definition

vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {

This is the function definition of `restoreMatrix`, which takes two vectors, `rowSum` and `colSum`, and returns a 2D vector (matrix) of integers.

2 : Variable Initialization

    int m = rowSum.size(), n = colSum.size();

Initialize variables `m` and `n` to store the sizes of the `rowSum` and `colSum` vectors, respectively. These values will be used to determine the number of rows and columns of the resulting matrix.

3 : Matrix Initialization

    vector<vector<int>> ans(m, vector<int>(n, 0));

Create a 2D vector `ans` initialized with zeros. This matrix will eventually hold the values where the row and column sums are satisfied.

4 : Loop

    for(int i = 0; i < m ;i++)

Start a loop over the rows of the matrix. The loop runs from `i = 0` to `i = m-1`.

5 : Loop

    for(int j = 0; j < n; j++) {

Start a nested loop over the columns of the matrix. The loop runs from `j = 0` to `j = n-1`.

6 : Matrix Assignment

        ans[i][j] = min(rowSum[i], colSum[j]);

At each position `ans[i][j]`, assign the minimum of the remaining values in `rowSum[i]` and `colSum[j]`. This ensures that the values placed in the matrix maintain the row and column sum constraints.

7 : Update

        rowSum[i]-= ans[i][j];

After assigning a value to `ans[i][j]`, decrement the corresponding row sum (`rowSum[i]`) by the assigned value.

8 : Update

        colSum[j]-= ans[i][j];

Similarly, decrement the corresponding column sum (`colSum[j]`) by the assigned value in `ans[i][j]`.

9 : Return

    return ans;

After the matrix is filled with appropriate values, return the resulting matrix `ans`.

Best Case: O(m * n)

Average Case: O(m * n)

Worst Case: O(m * n)

Description: The best, average, and worst case all involve iterating over the entire matrix, resulting in O(m * n) time complexity.

Best Case: O(m * n)

Worst Case: O(m * n)

Description: We need to store the matrix, so the space complexity is O(m * n), where m and n are the dimensions of the matrix.

Leetcode 1605: Find Valid Matrix Given Row and Column Sums

Explore →