Problem

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

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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:

1
2
3
4

Input: rowSum = [5,7,10], colSum = [8,6,8]
Output: [ [0,5,0],
          [6,1,0],
          [2,0,8] ]

Solution

Method 1 - Greedy

Here’s a step-by-step approach to constructing such a matrix:

  1. Initialize an empty matrix with dimensions based on the lengths of rowSum and colSum.
  2. Iteratively fill the matrix by selecting the smallest possible value that can be placed in the current cell (i, j) without violating the remaining sums for the current row and column.
  3. Update the rowSum and colSum accordingly and move to the next cell.

Here is the video explanation of the same:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Solution {

	public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
		int m = rowSum.length;
		int n = colSum.length;

		// Initialize a 2D array with dimensions m x n filled with zeros
		int[][] matrix = new int[m][n];

		// Fill the matrix
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				// Determine the value to place in cell (i, j)
				int value = Math.min(rowSum[i], colSum[j]);
				// Place the value in the matrix
				matrix[i][j] = value;

				rowSum[i] -= value;
				colSum[j] -= value;
			}
		}

		return matrix;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def restoreMatrix(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):
            # Determine the value to place in cell (i, j)
            value = min(rowSum[i], colSum[j])
            # Place the value in the matrix
            matrix[i][j] = value

            # Update the row and column sums
            rowSum[i] -= value
            colSum[j] -= value

    return matrix

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(1), as we don’t use any extra space but O(m*n) if we count the output matrix we return.