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

Array Matrix

Prompt

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.

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] <= 10⁸
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

Get the dimensions of the matrix, R = rowSum.length and C = colSum.length.
Create a result matrix matrix of size R x C and initialize all its elements to zero.
Iterate through each row i from 0 to R-1.
Inside the row loop, iterate through each column j from 0 to C-1.
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.
Assign this value to the matrix: matrix[i][j] = val.
Update the remaining sums by subtracting the placed value: rowSum[i] -= val and colSum[j] -= val.
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.

1class Solution {2    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {3        int R = rowSum.length;4        int C = colSum.length;5        int[][] matrix = new int[R][C];6 7        for (int i = 0; i < R; i++) {8            for (int j = 0; j < C; j++) {9                int val = Math.min(rowSum[i], colSum[j]);10                matrix[i][j] = val;11                rowSum[i] -= val;12                colSum[j] -= val;13            }14        }15        return matrix;16    }17}

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.

This is an optimized version of the greedy strategy. Instead of iterating through every cell, we use two pointers, i for the current row and j for the current column. We fill one cell matrix[i][j] at a time and then advance either the row pointer i or the column pointer j based on which sum (row or column) is satisfied. This avoids unnecessary iterations over cells that will be zero.

Algorithm

Get the dimensions of the matrix, R = rowSum.length and C = colSum.length.
Create a result matrix matrix of size R x C initialized to zeros.
Initialize two pointers: a row pointer i = 0 and a column pointer j = 0.
Loop while i < R and j < C.
In each iteration, determine the value for matrix[i][j] as val = min(rowSum[i], colSum[j]).
Place this value in the matrix: matrix[i][j] = val.
Update the remaining sums: rowSum[i] -= val and colSum[j] -= val.
Check if a row or column sum is satisfied. If rowSum[i] is now 0, it means row i is complete, so we advance the row pointer: i++.
Similarly, if colSum[j] is now 0, column j is complete, so we advance the column pointer: j++. Note that both can be true, in which case both pointers advance.
Continue until either i or j goes out of bounds.
Return the matrix.

Walkthrough

This approach improves upon the previous one by recognizing that once a row or column sum becomes zero, we don't need to consider its remaining cells (they will all be zero). We use a row pointer i and a column pointer j, starting at (0,0). In each step, we fill matrix[i][j] with min(rowSum[i], colSum[j]). This assignment will fully satisfy either the remaining requirement for row i or for column j (or both). If rowSum[i] becomes zero, we are done with this row and can move to the next by incrementing i. If colSum[j] becomes zero, we are done with this column and can move to the next by incrementing j. This way, we traverse a path through the matrix, making R + C - 1 decisions at most, rather than R * C. This leads to a more efficient linear time complexity.

1class Solution {2    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {3        int R = rowSum.length;4        int C = colSum.length;5        int[][] matrix = new int[R][C];6        7        int i = 0, j = 0;8        while (i < R && j < C) {9            int val = Math.min(rowSum[i], colSum[j]);10            matrix[i][j] = val;11            12            rowSum[i] -= val;13            colSum[j] -= val;14            15            if (rowSum[i] == 0) {16                i++;17            }18            if (colSum[j] == 0) {19                j++;20            }21        }22        23        return matrix;24    }25}

Complexity

Time

O(R + C) - In each step of the while loop, we increment either `i` or `j` (or both). `i` traverses from `0` to `R`, and `j` from `0` to `C`. The total number of iterations is bounded by `R + C`.

Space

O(R * C) - Required for the output matrix. Auxiliary space is O(1) if input arrays can be modified.

Trade-offs

Pros

Highly efficient with a linear time complexity with respect to the matrix dimensions.
Optimal solution for this problem under the given constraints.

Cons

The logic is slightly more complex to reason about compared to the simple nested loop approach, but it is still quite intuitive.

Solutions

Solution

1class 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 ; } }

1/** * @param {number[]} rowSum * @param {number[]} colSum * @return {number[][]} */ var restoreMatrix =2  function (rowSum, colSum) {3    const m = rowSum.length;4    const n = colSum.length;5    const ans = Array.from(new Array(m), () => new Array(n).fill(0));6    for (let i = 0; i < m; i++) {7      for (let j = 0; j < n; j++) {8        const x = Math.min(rowSum[i], colSum[j]);9        ans[i][j] = x;10        rowSum[i] -= x;11        colSum[j] -= x;12      }13    }14    return ans;15  };

1class Solution { public: vector < vector < int >> restoreMatrix ( vector < int >& rowSum , vector < int >& colSum ) { int m = rowSum . size (), n = colSum . size (); vector < vector < int >> ans ( m , vector < int > ( n )); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int x = min ( rowSum [ i ], colSum [ j ]); ans [ i ][ j ] = x ; rowSum [ i ] -= x ; colSum [ j ] -= x ; } } return ans ; } };

1class Solution : def restoreMatrix ( self , rowSum : List [ int ], colSum : List [ int ]) -> List [ List [ int ]]: m , n = len ( rowSum ), len ( colSum ) ans = [[ 0 ] * n for _ in range ( m )] for i in range ( m ): for j in range ( n ): x = 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 problem