1605. Find Valid Matrix Given Row and Column Sums

Hint

class Solution {
public:
    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum)
    {
        // Vectors to keep track of the current sum of elements in each row and column

        // Initialize the matrix with dimensions m x n filled with zeros

        // Fill the matrix with appropriate values
        for ()
        {
            for ()
            {
                // Calculate the value to place at matrix[i][j]
                // It should be the minimum of the remaining row sum and column sum

                // Update the current sums for the row and column
            }
        }
    }
};

class Solution {
public:
    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum)
    {
        int m = rowSum.size(), n = colSum.size();

        vector<int> curRowSum(m);
        vector<int> curColSum(n);

        vector<vector<int>> matrix(m, vector<int>(n));

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                matrix[i][j] = min(rowSum[i] - curRowSum[i], colSum[j] - curColSum[j]);
                curRowSum[i] += matrix[i][j];
                curColSum[j] += matrix[i][j];
            }
        }
        return matrix;
    }
};

• T: $O(m * n)$
• S: $O(m + n)$