> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find Valid Matrix Given Row and Column Sums

> Tested Python solution for LeetCode 1605 with 19 pytest cases. Generate a practice environment with lcpy.

LeetCode 1605, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Greedy](/catalog/topics/greedy), [Matrix](/catalog/topics/matrix), Flow Network. [View on LeetCode](https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/description/).

Generate this problem as a practice environment: tested reference solution, 19 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1605   # by problem number
lcpy gen -s find_valid_matrix_given_row_and_column_sums   # by problem name
```

## Problem

You are given two arrays `rowSum` and `colSum` of non-negative integers where `rowSum[i]` is the sum of the elements in the `i<sup>th</sup>` row and `colSum[j]` is the sum of the elements of the `j<sup>th</sup>` 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.

### Examples

```
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]]
```

```
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] <= 10^8`
* `sum(rowSum) == sum(colSum)`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_valid_matrix_given_row_and_column_sums/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_valid_matrix_given_row_and_column_sums/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(rows * cols) - each cell is filled at most once by the two-pointer sweep
    # Space: O(1) extra (the output matrix is not counted)
    def restore_matrix(self, row_sum: list[int], col_sum: list[int]) -> list[list[int]]:
        rs = list(row_sum)
        cs = list(col_sum)
        rows, cols = len(rs), len(cs)
        matrix = [[0] * cols for _ in range(rows)]
        r = 0
        c = 0
        while r < rows and c < cols:
            value = min(rs[r], cs[c])
            matrix[r][c] = value
            rs[r] -= value
            cs[c] -= value
            if rs[r] == 0:
                r += 1
            if cs[c] == 0:
                c += 1
        return matrix
```

## Complexity

| Time | Space |
| - | - |
| O(rows \* cols) - each cell is filled at most once by the two-pointer sweep | O(1) extra (the output matrix is not counted) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.