# Find Valid Matrix Given Row and Column Sums
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums)
Canonical: https://scaleengineer.com/dsa/problems/find-valid-matrix-given-row-and-column-sums
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Matrix
---
## Problem
You are given two arrays `rowSum` and `colSum` of non-negative integers where `rowSum[i]` is the sum of the elements in the `ith` row and `colSum[j]` is the sum of the elements of the `jth` column of a 2D matrix. In other words, you do not know the elements of the matrix, but you do know the sums of each row and column.

Find any matrix of **non-negative** integers of size `rowSum.length x colSum.length` that satisfies the `rowSum` and `colSum` requirements.

Return _a 2D array representing **any** matrix that fulfills the requirements_. It's guaranteed that **at least one** matrix that fulfills the requirements exists.

**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)`

# Approaches
## Greedy Approach with Nested Loops
This approach involves iterating through each cell of the matrix, from `(0,0)` to `(R-1, C-1)`. For each cell `(i, j)`, we greedily place the largest possible value that doesn't violate the row and column sum constraints. The largest possible value for `matrix[i][j]` is the minimum of the *remaining* sum required for row `i` and the *remaining* sum required for column `j`.
**Time:** O(R * C) - Where `R` is the number of rows and `C` is the number of columns. We must visit every cell in the `R x C` matrix once. · **Space:** O(R * C) - This is required to store the resulting matrix. If the output matrix is not considered extra space, the space complexity is O(1) assuming the input arrays can be modified, or O(R + C) if copies are needed.
**Pros:** The logic is very straightforward and easy to understand.; It's a simple and direct implementation of the greedy idea.
**Cons:** Less efficient than the optimized two-pointer approach, especially for large matrices, as it iterates through every cell regardless of whether a row or column sum has already been satisfied.
### Explanation
The core idea is to build the matrix cell by cell in a systematic order, like a standard row-major or column-major traversal. We initialize an `R x C` matrix with zeros, where `R` is `rowSum.length` and `C` is `colSum.length`. We then use nested loops to visit every cell `(i, j)`. At each cell, we make a greedy choice. The value `matrix[i][j]` must contribute to `rowSum[i]` and `colSum[j]`. To ensure we don't exceed these sums and keep the elements non-negative, we set `matrix[i][j]` to the minimum of the current `rowSum[i]` and `colSum[j]`. After setting `matrix[i][j]`, we update the remaining required sums for that row and column by subtracting the value we just placed. This process is repeated for all `R*C` cells. Because the problem guarantees a solution exists, this greedy strategy is guaranteed to find one. By the end of the traversal, all row and column sum constraints will be met.

```java
class Solution {
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int R = rowSum.length;
        int C = colSum.length;
        int[][] matrix = new int[R][C];

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                int val = Math.min(rowSum[i], colSum[j]);
                matrix[i][j] = val;
                rowSum[i] -= val;
                colSum[j] -= val;
            }
        }
        return matrix;
    }
}
```
### Algorithm
1. Get the dimensions of the matrix, `R = rowSum.length` and `C = colSum.length`.
2. Create a result matrix `matrix` of size `R x C` and initialize all its elements to zero.
3. Iterate through each row `i` from `0` to `R-1`.
4. Inside the row loop, iterate through each column `j` from `0` to `C-1`.
5. For the current cell `(i, j)`, calculate the value to be placed as `val = min(rowSum[i], colSum[j])`. Here, `rowSum[i]` and `colSum[j]` represent the remaining required sums for the current row and column.
6. Assign this value to the matrix: `matrix[i][j] = val`.
7. Update the remaining sums by subtracting the placed value: `rowSum[i] -= val` and `colSum[j] -= val`.
8. After the loops complete, return the `matrix`.

## Optimized Greedy Approach with Two Pointers
This is an optimized version of the greedy strategy. Instead of iterating through every cell, we use two pointers, `i` for the current row and `j` for the current column. We fill one cell `matrix[i][j]` at a time and then advance either the row pointer `i` or the column pointer `j` based on which sum (row or column) is satisfied. This avoids unnecessary iterations over cells that will be zero.
**Time:** O(R + C) - In each step of the while loop, we increment either `i` or `j` (or both). `i` traverses from `0` to `R`, and `j` from `0` to `C`. The total number of iterations is bounded by `R + C`. · **Space:** O(R * C) - Required for the output matrix. Auxiliary space is O(1) if input arrays can be modified.
**Pros:** Highly efficient with a linear time complexity with respect to the matrix dimensions.; Optimal solution for this problem under the given constraints.
**Cons:** The logic is slightly more complex to reason about compared to the simple nested loop approach, but it is still quite intuitive.
### Explanation
This approach improves upon the previous one by recognizing that once a row or column sum becomes zero, we don't need to consider its remaining cells (they will all be zero). We use a row pointer `i` and a column pointer `j`, starting at `(0,0)`. In each step, we fill `matrix[i][j]` with `min(rowSum[i], colSum[j])`. This assignment will fully satisfy either the remaining requirement for row `i` or for column `j` (or both). If `rowSum[i]` becomes zero, we are done with this row and can move to the next by incrementing `i`. If `colSum[j]` becomes zero, we are done with this column and can move to the next by incrementing `j`. This way, we traverse a path through the matrix, making `R + C - 1` decisions at most, rather than `R * C`. This leads to a more efficient linear time complexity.

```java
class Solution {
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int R = rowSum.length;
        int C = colSum.length;
        int[][] matrix = new int[R][C];
        
        int i = 0, j = 0;
        while (i < R && j < C) {
            int val = Math.min(rowSum[i], colSum[j]);
            matrix[i][j] = val;
            
            rowSum[i] -= val;
            colSum[j] -= val;
            
            if (rowSum[i] == 0) {
                i++;
            }
            if (colSum[j] == 0) {
                j++;
            }
        }
        
        return matrix;
    }
}
```
### Algorithm
1. Get the dimensions of the matrix, `R = rowSum.length` and `C = colSum.length`.
2. Create a result matrix `matrix` of size `R x C` initialized to zeros.
3. Initialize two pointers: a row pointer `i = 0` and a column pointer `j = 0`.
4. Loop while `i < R` and `j < C`.
5. In each iteration, determine the value for `matrix[i][j]` as `val = min(rowSum[i], colSum[j])`.
6. Place this value in the matrix: `matrix[i][j] = val`.
7. Update the remaining sums: `rowSum[i] -= val` and `colSum[j] -= val`.
8. Check if a row or column sum is satisfied. If `rowSum[i]` is now `0`, it means row `i` is complete, so we advance the row pointer: `i++`.
9. Similarly, if `colSum[j]` is now `0`, column `j` is complete, so we advance the column pointer: `j++`. Note that both can be true, in which case both pointers advance.
10. Continue until either `i` or `j` goes out of bounds.
11. Return the `matrix`.

# Solutions
### Java

```java
class Solution { public int [][] restoreMatrix ( int [] rowSum , int [] colSum ) { int m = rowSum . length ; int n = colSum . length ; int [][] ans = 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 ]); ans [ i ][ j ] = x ; rowSum [ i ] -= x ; colSum [ j ] -= x ; } } return ans ; } }
```

### JavaScript

```javascript
/** * @param {number[]} rowSum * @param {number[]} colSum * @return {number[][]} */ var restoreMatrix =
  function (rowSum, colSum) {
    const m = rowSum.length;
    const n = colSum.length;
    const ans = Array.from(new Array(m), () => new Array(n).fill(0));
    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        const x = Math.min(rowSum[i], colSum[j]);
        ans[i][j] = x;
        rowSum[i] -= x;
        colSum[j] -= x;
      }
    }
    return ans;
  };

```

### CPP

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

### Python

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