# [1605\. Find Valid Matrix Given Row and Column Sums](https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/)

:::spoiler 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
            }
        }
    }
};

:::

:::spoiler Solution

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)$
:::