Find Valid Matrix Given Row and Column Sums

Find Valid Matrix Given Row and Column Sums - 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-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.

Input & Output

Example 1 — Basic Case

$ Input: rowSum = [3,8], colSum = [4,7]

› Output: [[0,3],[4,4]]

💡 Note: Row 0: 0+3=3 ✓, Row 1: 4+4=8 ✓, Col 0: 0+4=4 ✓, Col 1: 3+4=7 ✓

Example 2 — Square Matrix

$ Input: rowSum = [5,7,10], colSum = [8,6,8]

› Output: [[0,5,0],[6,1,0],[2,0,8]]

💡 Note: Each row sum and column sum matches the requirements. Greedy approach fills optimally.

Example 3 — Single Row

$ Input: rowSum = [14], colSum = [9,5]

› Output: [[9,5]]

💡 Note: Single row case: 9+5=14 ✓, columns sum to [9] and [5] respectively.

Constraints

1 ≤ rowSum.length, colSum.length ≤ 500
0 ≤ rowSum[i], colSum[i] ≤ 10⁸
sum(rowSum) == sum(colSum)

Visualization

Tap to expand

Understanding the Visualization

Input

Given rowSum=[3,8] and colSum=[4,7] - need 2x2 matrix

Process

Greedily fill each cell with min(remaining_row, remaining_col)

Output

Result matrix [[0,3],[4,4]] satisfies all constraints

Key Takeaway

🎯 Key Insight: Greedy approach works because placing min(remaining_row, remaining_col) at each position ensures we never exceed constraints while guaranteeing a solution exists.

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is using a greedy approach where each cell gets the minimum of its remaining row and column sums. This guarantees a valid solution while being optimal. Best approach is Greedy Algorithm with Time: O(m×n), Space: O(m×n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach	O(m×n)	O(m×n)	Fill each cell with minimum of remaining row and column sums
Brute Force - Try All Combinations	O((max_sum)^(m×n))	O(m×n)	Generate all possible matrices and check which ones satisfy the constraints

Greedy Approach — Algorithm Steps

Initialize result matrix with zeros
For each cell (i,j), set value = min(remaining_row[i], remaining_col[j])
Update remaining sums by subtracting the placed value
Continue until all cells are filled

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with empty matrix and track remaining sums

Fill Greedily

For each cell, place min(remaining_row, remaining_col)

Update

Subtract placed value from remaining sums

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** solution(int* rowSum, int rowSumSize, int* colSum, int colSumSize, int* returnSize, int** returnColumnSizes) {
    int m = rowSumSize, n = colSumSize;
    *returnSize = m;
    *returnColumnSizes = (int*)malloc(m * sizeof(int));
    
    int** result = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        result[i] = (int*)calloc(n, sizeof(int));
        (*returnColumnSizes)[i] = n;
    }
    
    // Create copies to track remaining sums
    int* remainingRow = (int*)malloc(m * sizeof(int));
    int* remainingCol = (int*)malloc(n * sizeof(int));
    
    for (int i = 0; i < m; i++) remainingRow[i] = rowSum[i];
    for (int i = 0; i < n; i++) remainingCol[i] = colSum[i];
    
    // Fill matrix greedily
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // Place minimum of remaining row and column sums
            int val = remainingRow[i] < remainingCol[j] ? remainingRow[i] : remainingCol[j];
            result[i][j] = val;
            
            // Update remaining sums
            remainingRow[i] -= val;
            remainingCol[j] -= val;
        }
    }
    
    free(remainingRow);
    free(remainingCol);
    
    return result;
}

int main() {
    // Simplified parsing for demonstration
    int rowSum[] = {3, 8};
    int colSum[] = {4, 7};
    int returnSize;
    int* returnColumnSizes;
    
    int** result = solution(rowSum, 2, colSum, 2, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Single pass through all matrix cells

✓ Linear Growth

Space Complexity

O(m×n)

Space for the result matrix only

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler