1605. Find Valid Matrix Given Row and Column Sums

📝 Problem Details

• Title: 1605. Find Valid Matrix Given Row and Column Sums
• Link: https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/
• Difficulty: Medium
• Tags/Categories: Arrays Matrix Greedy

💭What Were My Initial Thoughts?

- intuition behind the problem is simple to follow 
- possibly being greedy, and taking the highest possible value that is <= to the colSum and rowSum for that particular position

🤔What Did I Struggle With?

after the first iteration, how do we keep track of the sum remaining for the next position 

💡 Explanation of Solution

- initialize a matrix of size n*m (size of rowSum and colSum vectors respectively) with their values to 0
- nested loop iterating through rows and cols
	- calculate the maxValue you can place in the current position ~ min(rowSum[i], colSum[i])
	- place that value in the position in the matrix
	- decrement the row and col sums with by that value, leaving the remaining for the next positions

⌛ Complexity Analysis

Time Complexity: O(n*m) where n is the number of rows and m is the number of columns in the matrix
Space Complexity: O(n*m) for creation and population of the matrix

💻 Implementation of Solution

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