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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Valid Matrix Given Row and Column Sums

Number: 1711

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given two arrays, rowSum and colSum, where rowSum[i] is the sum of the iᵗʰ row and colSum[j] is the sum of the jᵗʰ column of an unknown matrix, construct any matrix of non-negative integers that meets these row and column sum requirements. It is guaranteed that at least one valid solution exists.

Key Insights

  • Use a greedy approach by filling the matrix cell-by-cell.
  • At each cell (i, j), assign the minimum of the current row sum (rowSum[i]) and column sum (colSum[j]).
  • Subtract the assigned value from both rowSum[i] and colSum[j].
  • Continue processing the matrix in a row-major order until all cells are filled, which naturally satisfies both row and column requirements.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Space Complexity: O(m * n), which is used for storing the resulting matrix.

Solution

The problem is solved using a greedy strategy. We initialize a matrix with zeros and process each cell in a row-by-row manner. For each cell (i, j), we calculate the minimum of the remaining required sum for row i and column j. This value is placed in the cell, and the respective row and column sums are decreased by this amount. This process continues until the entire matrix is constructed, and the resulting matrix meets the required row and column sums.

Code Solutions

# Python solution for constructing the valid matrix.

def restoreMatrix(rowSum, colSum):
    # Get the dimensions of the matrix.
    num_rows = len(rowSum)
    num_cols = len(colSum)
    
    # Initialize the matrix with 0's.
    matrix = [[0] * num_cols for _ in range(num_rows)]
    
    # Process each cell in the matrix.
    for i in range(num_rows):
        for j in range(num_cols):
            # Determine the value for the current cell as the minimum
            # of the remaining row and column sums.
            value = min(rowSum[i], colSum[j])
            matrix[i][j] = value
            # Update the corresponding sums.
            rowSum[i] -= value
            colSum[j] -= value
            
    return matrix

# Example usage:
# rowSum = [3,8] and colSum = [4,7] should produce a valid matrix.
print(restoreMatrix([3,8], [4,7]))
← Back to All Questions