We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Valid Matrix Given Row and Column Sums

Difficulty: Medium

Problem Description

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.

Key Insights

  • The matrix must be filled in such a way that the sum of each row equals the corresponding value in rowSum and the sum of each column equals the corresponding value in colSum.
  • A greedy approach can be utilized by iterating through the matrix and filling it based on the minimum of the remaining row and column sums.
  • The problem guarantees that a valid matrix exists, thus we can focus on constructing one without worrying about impossible cases.

Space and Time Complexity

Time Complexity: O(m * n) where m is the length of rowSum and n is the length of colSum.
Space Complexity: O(m * n) for storing the resulting matrix.

Solution

To solve the problem, we can use a greedy approach. We will create a 2D matrix initialized with zeros. We will iterate through each cell of the matrix and fill it with the minimum of the remaining row sum and column sum for that position. After filling a cell, we will update the corresponding row and column sums by subtracting the value placed in that cell. This process continues until we have filled the entire matrix according to the constraints of rowSum and colSum.

Code Solutions

def fillMatrix(rowSum, colSum):
    m, n = len(rowSum), len(colSum)
    matrix = [[0] * n for _ in range(m)]
    
    for i in range(m):
        for j in range(n):
            # Fill the cell with the minimum of the remaining row and column sums
            value = min(rowSum[i], colSum[j])
            matrix[i][j] = value
            
            # Update the remaining sums
            rowSum[i] -= value
            colSum[j] -= value
            
    return matrix
← Back to All Questions