1605. Find Valid Matrix Given Row and Column Sums

Medium

You are given two arrays rowSum and colSum of non-negative integers where rowSum[i] is the sum of the elements in the i^th row and colSum[j] is the sum of the elements of the j^th 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] <= 10⁸
sum(rowSum) == sum(colSum)

Hint:

Find the smallest rowSum or colSum, and let it be x. Place that number in the grid, and subtract x from rowSum and colSum. Continue until all the sums are satisfied.

Solution:

To solve this problem, we can follow these steps:

Start with an empty matrix of size rowSum.length x colSum.length initialized with zeros.
Iterate over the matrix and at each position (i, j), place the minimum value between rowSum[i] and colSum[j] to ensure non-negative values.
Update rowSum[i] and colSum[j] by subtracting the placed value.
Continue until all elements of rowSum and colSum are zero.

Let's implement this solution in PHP: 1605. Find Valid Matrix Given Row and Column Sums

<?php
// Example usage:
$rowSum1 = [3, 8];
$colSum1 = [4, 7];
print_r(restoreMatrix($rowSum1, $colSum1)); 
// Output: [[3, 0], [1, 7]]

$rowSum2 = [5, 7, 10];
$colSum2 = [8, 6, 8];
print_r(restoreMatrix($rowSum2, $colSum2));
// Output: [[0, 5, 0], [6, 1, 0], [2, 0, 8]]

?>

Explanation:

Initialization:
- Create a matrix of size m x n filled with zeros.
- m is the length of rowSum and n is the length of colSum.
Iterative Filling:
- For each cell (i, j), determine the value to be placed in the matrix as the minimum of rowSum[i] and colSum[j].
- Place this value in the matrix at (i, j).
- Subtract this value from both rowSum[i] and colSum[j].
Continue Until Completion:
- Repeat the process until all elements in rowSum and colSum are reduced to zero.

This method ensures that the constructed matrix meets the row and column sum requirements while maintaining non-negative values for all elements.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub