Code Implementation

class Solution:
    def restoreMatrix(self, rowSum, colSum):
        m, n = len(rowSum), len(colSum)
        res = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                x = min(rowSum[i], colSum[j])
                res[i][j] = x
                rowSum[i] -= x
                colSum[j] -= x
        return res
      

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

class Solution {
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int m = rowSum.length, n = colSum.length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int x = Math.min(rowSum[i], colSum[j]);
                res[i][j] = x;
                rowSum[i] -= x;
                colSum[j] -= x;
            }
        }
        return res;
    }
}
      

var restoreMatrix = function(rowSum, colSum) {
    let m = rowSum.length, n = colSum.length;
    let res = Array.from({length: m}, () => Array(n).fill(0));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let x = Math.min(rowSum[i], colSum[j]);
            res[i][j] = x;
            rowSum[i] -= x;
            colSum[j] -= x;
        }
    }
    return res;
};
      

Problem Description

You are given two integer arrays, rowSum and colSum, representing the row and column sums of a matrix you need to reconstruct. Your task is to build a non-negative integer matrix matrix with dimensions m x n (where m is the length of rowSum and n is the length of colSum) such that:

• The sum of elements in the i-th row equals rowSum[i]
• The sum of elements in the j-th column equals colSum[j]
• All elements are non-negative integers
• You must return any valid matrix that satisfies these constraints

You do not need to find all possible matrices—just one valid solution. Each element in the matrix may be used as needed, as long as the row and column sums are satisfied.

Thought Process

At first glance, this problem might seem to require trying all possible combinations of numbers to fill the matrix so that both the row and column sums are achieved. This brute-force approach would involve generating all possible matrices and checking if their row and column sums match the given arrays, which is computationally infeasible for large matrices.

However, upon closer inspection, we realize that the order in which we fill the matrix doesn't matter as long as we respect the row and column sum constraints. This suggests a greedy approach: at each cell, we can assign the largest value possible without exceeding the remaining row or column sum. This way, we ensure that we never "overdraw" any row or column, and we can always fill the next cell with a valid non-negative integer.

This shift from brute-force to a greedy, cell-by-cell filling strategy is the key insight that makes the problem tractable.

Solution Approach

Let's break down the step-by-step algorithm for constructing the matrix:

1. Initialize the Matrix: Create a matrix res of size m x n filled with zeros.
2. Iterate Over Each Cell: For each cell (i, j) in the matrix, do the following:
   • Determine the maximum value you can put in res[i][j] without exceeding the remaining sum for row i or column j. This is min(rowSum[i], colSum[j]).
   • Assign this value to res[i][j].
   • Subtract this value from both rowSum[i] and colSum[j] to update the remaining sums for the current row and column.
3. Repeat: Continue this process for all cells in the matrix. Each time, the remaining row and column sums are adjusted, ensuring the constraints are always respected.
4. Return the Matrix: Once all cells are filled, return the matrix. By construction, the sums of each row and column will match the given arrays.

This approach works because at each step, we never exceed the required sum for any row or column, and by always assigning as much as possible to each cell, we ensure that the remaining sums can be distributed among the remaining cells.

Example Walkthrough

Let's walk through an example to see how the algorithm works in practice.

Suppose rowSum = [3, 8] and colSum = [4, 7].

1. Start with a 2x2 matrix filled with zeros:
   [[0, 0], [0, 0]]
2. Cell (0, 0):
   • rowSum[0] = 3, colSum[0] = 4
   • Assign x = min(3, 4) = 3
   • Update matrix: [[3, 0], [0, 0]]
   • rowSum becomes [0, 8], colSum becomes [1, 7]
3. Cell (0, 1):
   • rowSum[0] = 0, colSum[1] = 7
   • Assign x = min(0, 7) = 0
   • Update matrix: [[3, 0], [0, 0]]
   • rowSum becomes [0, 8], colSum becomes [1, 7]
4. Cell (1, 0):
   • rowSum[1] = 8, colSum[0] = 1
   • Assign x = min(8, 1) = 1
   • Update matrix: [[3, 0], [1, 0]]
   • rowSum becomes [0, 7], colSum becomes [0, 7]
5. Cell (1, 1):
   • rowSum[1] = 7, colSum[1] = 7
   • Assign x = min(7, 7) = 7
   • Update matrix: [[3, 0], [1, 7]]
   • rowSum becomes [0, 0], colSum becomes [0, 0]
6. The final matrix is [[3, 0], [1, 7]], which satisfies all row and column sums.

Time and Space Complexity

Brute-force Approach:
If we tried all possible ways to fill the matrix, the time complexity would be exponential, specifically O(k^(m*n)), where k is the maximum possible value in any cell. This is not practical for even modestly sized matrices.

Greedy Solution (Optimized):
Our greedy approach iterates over each cell exactly once. For an m x n matrix:

• Time Complexity: O(m * n), because we visit each cell once and perform constant-time operations per cell.
• Space Complexity: O(m * n), for storing the resulting matrix.

The algorithm is efficient and scales well for large matrices.

Summary

The key insight in this problem is realizing that a greedy, cell-by-cell filling strategy allows us to efficiently construct a valid matrix that matches the given row and column sums. By always assigning the minimum of the remaining row and column sums to each cell, we ensure that constraints are maintained and a solution is always possible. This approach is simple, elegant, and highly efficient compared to brute-force methods.