Find Valid Matrix Given Row and Column Sums

Problem Statement

In this problem, you are presented with two arrays: rowSum and colSum. Each of these arrays contains non-negative integers, where each entry rowSum[i] corresponds to the sum of the elements in the i-th row, and each colSum[j] corresponds to the sum of the elements in the j-th column of a theoretical 2D matrix. The task at hand is to construct any 2D matrix that matches these given row and column sums, using non-negative integers. This matrix must be of dimensions equal to the length of rowSum by the length of colSum. The requirement is to return a matrix such that each row and column sum up to the values specified in rowSum and colSum respectively. Importantly, the problem guarantees that at least one valid matrix configuration exists that satisfies the given conditions.

Examples

Example 1

Input:

rowSum = [3,8], colSum = [4,7]

Output:

[[3,0],
[1,7]]

Explanation:

0th row: 3 + 0 = 3 == rowSum[0]
1st row: 1 + 7 = 8 == rowSum[1]
0th column: 3 + 1 = 4 == colSum[0]
1st column: 0 + 7 = 7 == colSum[1]
The row and column sums match, and all matrix elements are non-negative.
Another possible matrix is: [[1,2],
[3,5]]

Example 2

Input:

rowSum = [5,7,10], colSum = [8,6,8]

Output:

[[0,5,0],
[6,1,0],
[2,0,8]]

Constraints

• 1 <= rowSum.length, colSum.length <= 500
• 0 <= rowSum[i], colSum[i] <= 108
• sum(rowSum) == sum(colSum)

Approach and Intuition

The problem is essentially about distributing the sum values among the matrix elements so that the final sums of both rows and columns align with the provided arrays rowSum and colSum. Here's a general approach to forming such a matrix:

1. Initialize the matrix of size rowSum.length x colSum.length with all zeros.
2. Proceed row-by-row, trying to consume the entire rowSum for each respective row:
   • For each row, iterate through each column.
   • Allocate to the matrix cell the minimum of rowSum for that row and colSum for that column. This choice ensures that neither row nor column sum constraints are violated.
   • Subtract the allocated number simultaneously from the corresponding rowSum and colSum values, indicating that a portion of the total required sum has been fulfilled.
3. This procedure effectively "uses up" the sum constraints in a top-down and left-to-right approach, ensuring all constraints are met.
4. Continue the process until all entries in both rowSum and colSum are zero, implying that a valid matrix formation has been achieved.
5. Return the constructed matrix.

This strategy works because through each allocation, it ensures that neither the row nor the column exceed its corresponding sum requirement. At each point, the decrease in rowSum and colSum exactly corresponds to the values placed in the matrix, thus maintaining the integrity of the row and column sums.

Solutions

class Solution {
public:
    vector<vector<int>> reconstructMatrix(vector<int>& rowSum,
                                          vector<int>& colSum) {
        int rows = rowSum.size();
        int cols = colSum.size();
    
        vector<vector<int>> matrix(rows, vector<int>(cols, 0));
        int rowIdx = 0, colIdx = 0;
    
        while (rowIdx < rows && colIdx < cols) {
            matrix[rowIdx][colIdx] = min(rowSum[rowIdx], colSum[colIdx]);
    
            rowSum[rowIdx] -= matrix[rowIdx][colIdx];
            colSum[colIdx] -= matrix[rowIdx][colIdx];
    
            rowSum[rowIdx] == 0 ? rowIdx++ : colIdx++;
        }
        return matrix;
    }
};