Scale Engineer

Find Valid Matrix Given Row and Column Sums

Med
#1476Time: O(R * C) - Where `R` is the number of rows and `C` is the number of columns. We must visit every cell in the `R x C` matrix once.Space: O(R * C) - This is required to store the resulting matrix. If the output matrix is not considered extra space, the space complexity is O(1) assuming the input arrays can be modified, or O(R + C) if copies are needed.
Patterns
Greedy
Data structures
ArrayMatrix

Prompt

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.

 

Example 1:

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:

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

 

Constraints:

  • 1 <= rowSum.length, colSum.length <= 500
  • 0 <= rowSum[i], colSum[i] <= 108
  • sum(rowSum) == sum(colSum)

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through each cell of the matrix, from (0,0) to (R-1, C-1). For each cell (i, j), we greedily place the largest possible value that doesn't violate the row and column sum constraints. The largest possible value for matrix[i][j] is the minimum of the remaining sum required for row i and the remaining sum required for column j.

Algorithm

  1. Get the dimensions of the matrix, R = rowSum.length and C = colSum.length.
  2. Create a result matrix matrix of size R x C and initialize all its elements to zero.
  3. Iterate through each row i from 0 to R-1.
  4. Inside the row loop, iterate through each column j from 0 to C-1.
  5. For the current cell (i, j), calculate the value to be placed as val = min(rowSum[i], colSum[j]). Here, rowSum[i] and colSum[j] represent the remaining required sums for the current row and column.
  6. Assign this value to the matrix: matrix[i][j] = val.
  7. Update the remaining sums by subtracting the placed value: rowSum[i] -= val and colSum[j] -= val.
  8. After the loops complete, return the matrix.

Walkthrough

The core idea is to build the matrix cell by cell in a systematic order, like a standard row-major or column-major traversal. We initialize an R x C matrix with zeros, where R is rowSum.length and C is colSum.length. We then use nested loops to visit every cell (i, j). At each cell, we make a greedy choice. The value matrix[i][j] must contribute to rowSum[i] and colSum[j]. To ensure we don't exceed these sums and keep the elements non-negative, we set matrix[i][j] to the minimum of the current rowSum[i] and colSum[j]. After setting matrix[i][j], we update the remaining required sums for that row and column by subtracting the value we just placed. This process is repeated for all R*C cells. Because the problem guarantees a solution exists, this greedy strategy is guaranteed to find one. By the end of the traversal, all row and column sum constraints will be met.

class Solution {    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {        int R = rowSum.length;        int C = colSum.length;        int[][] matrix = new int[R][C];         for (int i = 0; i < R; i++) {            for (int j = 0; j < C; j++) {                int val = Math.min(rowSum[i], colSum[j]);                matrix[i][j] = val;                rowSum[i] -= val;                colSum[j] -= val;            }        }        return matrix;    }}

Complexity

Time

O(R * C) - Where `R` is the number of rows and `C` is the number of columns. We must visit every cell in the `R x C` matrix once.

Space

O(R * C) - This is required to store the resulting matrix. If the output matrix is not considered extra space, the space complexity is O(1) assuming the input arrays can be modified, or O(R + C) if copies are needed.

Trade-offs

Pros

  • The logic is very straightforward and easy to understand.

  • It's a simple and direct implementation of the greedy idea.

Cons

  • Less efficient than the optimized two-pointer approach, especially for large matrices, as it iterates through every cell regardless of whether a row or column sum has already been satisfied.

Solutions

class Solution { public int [][] restoreMatrix ( int [] rowSum , int [] colSum ) { int m = rowSum . length ; int n = colSum . length ; int [][] ans = new int [ m ][ n ]; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int x = Math . min ( rowSum [ i ], colSum [ j ]); ans [ i ][ j ] = x ; rowSum [ i ] -= x ; colSum [ j ] -= x ; } } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem