Find Valid Matrix Given Row And Column Sums - Leetcode Solution

Problem Statement:

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 in 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.

If there are multiple answers, you may return any of them.

Solution:

The problem is a simple simulation based one. We need to create a matrix, which has the given row sums and column sums.

First, we create a matrix of size rowSum.length x colSum.length with all cells initialized to 0. Then, for each row and column, we fill the minimum of the row sum and column sum in the corresponding cell of the matrix, and subtract the filled value from the corresponding row sum and column sum.

We repeat this process until all row sums and column sums become 0. At each step, we check whether it is possible to fill the cell without violating the non-negativity constraint. We can check this by comparing the remaining row sums and column sums with the remaining cells that need to be filled.

We can implement this algorithm in the following way:

1. Initialize a matrix of size rowSum.length x colSum.length with all cells initialized to 0.
2. While rowSum and colSum are not both 0: a. Find a cell (i,j) where rowSum[i] and colSum[j] are both positive. b. Calculate the minimum possible value for the cell (i,j) as min(rowSum[i], colSum[j]). c. If the minimum possible value is negative, it means it is not possible to fill the cell without violating the non-negativity constraint. In this case, return an empty matrix as there is no valid matrix that satisfies the row sum and column sum constraints. d. Otherwise, fill the cell (i,j) with the minimum possible value, and subtract it from both rowSum[i] and colSum[j].
3. Return the matrix.

Here is the Python implementation:

def restoreMatrix(rowSum, colSum): n = len(rowSum) m = len(colSum) mat = [[0 for j in range(m)] for i in range(n)] while sum(rowSum) > 0 and sum(colSum) > 0: # Find a cell where both row sum and column sum are positive for i in range(n): for j in range(m): if mat[i][j] == 0 and rowSum[i] > 0 and colSum[j] > 0: # Calculate minimum possible value for this cell val = min(rowSum[i], colSum[j]) if val < 0: # It is not possible to fill the cell without violating non-negativity constraint return [] mat[i][j] = val rowSum[i] -= val colSum[j] -= val break else: continue break return mat

Time Complexity: O(nm), where n is the length of rowSum and m is the length of colSum.

Space Complexity: O(nm), to store the matrix.

1