LeetCode 1605 - Find Valid Matrix Given Row and Column Sums

LeetCode Problem 1605

Difficulty: 🟡 Medium
Topics: Array, Greedy, Matrix

Solution

Problem Understanding

The problem gives us two arrays:

• rowSum, where rowSum[i] represents the total sum required for row i
• colSum, where colSum[j] represents the total sum required for column j

Our task is to construct any matrix of non-negative integers such that:

1. Every row adds up to its corresponding value in rowSum
2. Every column adds up to its corresponding value in colSum

We are not required to find a unique matrix. Any valid matrix is acceptable.

Suppose rowSum = [3, 8] and colSum = [4, 7]. This means:

• The first row must total 3
• The second row must total 8
• The first column must total 4
• The second column must total 7

We must distribute values across the matrix so that all these constraints are simultaneously satisfied.

The constraints are important:

• Up to 500 rows and 500 columns
• Individual sums can be as large as 10^8
• Total row sum always equals total column sum

The final guarantee is extremely important. Since the total amount required by rows equals the total amount required by columns, at least one valid solution always exists.

A naive implementation could fail on several edge cases:

• Rows or columns with sum 0
• Large values requiring careful updates
• Uneven distributions where one row or column is exhausted early
• Large matrix sizes where inefficient backtracking would time out

Because the problem only asks for any valid matrix, we do not need optimization of the matrix contents themselves. We only need a correct construction.

Approaches

Brute Force Approach

A brute force solution would attempt to assign values to every cell while recursively checking whether the row and column sums remain valid.

At each position (i, j), we could try every possible value from 0 up to the minimum of the remaining row sum and column sum. Then we recursively continue filling the matrix.

This approach is correct because it explores all possible valid assignments. Eventually, one valid matrix will be found.

However, the number of possibilities grows exponentially. Even for moderately sized matrices, the search space becomes enormous. Since both dimensions can be up to 500, brute force backtracking is completely impractical.

Optimal Greedy Approach

The key observation is that for any cell (i, j), the maximum value we can safely place there is:

$$\min(rowSum[i], colSum[j])$$

If we place this amount:

• We satisfy as much as possible for both the current row and column
• At least one of the two constraints becomes fully satisfied
• We never violate non-negative requirements

This naturally suggests a greedy strategy.

For every cell:

1. Put the largest valid value possible
2. Subtract it from both the row and column requirements
3. Continue filling the matrix

Because the total sums are balanced, this process always succeeds.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(m × n)	Tries all possible assignments recursively
Optimal Greedy	O(m × n)	O(m × n)	Fills each cell once using greedy assignment

Algorithm Walkthrough

Step 1: Initialize the Result Matrix

Create an m x n matrix filled with zeros, where:

• m = len(rowSum)
• n = len(colSum)

This matrix will gradually be filled with valid values.

Step 2: Iterate Through Every Cell

Use nested loops:

• Outer loop for rows
• Inner loop for columns

At each position (i, j), determine how much value can be safely placed there.

Step 3: Compute the Maximum Valid Value

For cell (i, j):

value = min(rowSum[i], colSum[j])

We choose the minimum because:

• A row cannot exceed its remaining required sum
• A column cannot exceed its remaining required sum

This guarantees the assignment remains valid.

Step 4: Place the Value into the Matrix

Store the computed value into:

matrix[i][j] = value

This contributes to both the row total and column total.

Step 5: Update Remaining Sums

After assigning the value:

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

This tracks how much sum still needs to be distributed later.

Step 6: Continue Until All Cells Are Processed

Because each assignment reduces at least one remaining sum to zero, the algorithm steadily progresses toward completion.

Eventually:

• Every row sum becomes zero
• Every column sum becomes zero

The constructed matrix is therefore valid.

Why it works

The greedy strategy works because each cell assignment respects both remaining constraints simultaneously. By always placing the maximum feasible value, we guarantee that no future placement becomes impossible.

At every step:

• Row sums remain non-negative
• Column sums remain non-negative
• The total remaining row sum always equals the total remaining column sum

Since at least one constraint becomes satisfied after each placement, the process eventually terminates with a valid matrix.

Python Solution

from typing import List

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        rows = len(rowSum)
        cols = len(colSum)

        matrix = [[0] * cols for _ in range(rows)]

        for i in range(rows):
            for j in range(cols):
                value = min(rowSum[i], colSum[j])

                matrix[i][j] = value

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

        return matrix

The implementation begins by determining the matrix dimensions from the input arrays.

A result matrix initialized with zeros is created. This ensures every cell already contains a valid non-negative value before assignment.

The nested loops visit every matrix cell exactly once. For each cell, the algorithm computes the largest value that can safely fit using:

min(rowSum[i], colSum[j])

This value is inserted into the matrix, and both the row and column requirements are updated immediately.

Because the remaining sums are updated in place, the algorithm always knows exactly how much capacity remains for future cells.

Finally, the completed matrix is returned.

Go Solution

func restoreMatrix(rowSum []int, colSum []int) [][]int {
    rows := len(rowSum)
    cols := len(colSum)

    matrix := make([][]int, rows)

    for i := 0; i < rows; i++ {
        matrix[i] = make([]int, cols)

        for j := 0; j < cols; j++ {
            value := rowSum[i]
            if colSum[j] < value {
                value = colSum[j]
            }

            matrix[i][j] = value

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

    return matrix
}

The Go implementation follows the exact same greedy logic as the Python version.

One small difference is that Go does not provide a built in min function for integers, so the comparison is implemented manually with an if statement.

The matrix is created using slices of slices. Since Go slices are initialized with zero values automatically, every cell starts at 0.

Integer overflow is not an issue because the constraints fit safely within Go's standard integer range.

Worked Examples

Example 1

Input:

rowSum = [3, 8]
colSum = [4, 7]

Initial matrix:

	0	1
0	0	0
1	0	0

Iteration Details

Cell	rowSum	colSum	value placed	Matrix State
(0,0)	[3,8]	[4,7]	min(3,4)=3	[[3,0],[0,0]]
(0,1)	[0,8]	[1,7]	min(0,7)=0	[[3,0],[0,0]]
(1,0)	[0,8]	[1,7]	min(8,1)=1	[[3,0],[1,0]]
(1,1)	[0,7]	[0,7]	min(7,7)=7	[[3,0],[1,7]]

Final matrix:

[[3,0],
 [1,7]]

Example 2

Input:

rowSum = [5,7,10]
colSum = [8,6,8]

Iteration Details

Cell	rowSum	colSum	value placed
(0,0)	[5,7,10]	[8,6,8]	5
(0,1)	[0,7,10]	[3,6,8]	0
(0,2)	[0,7,10]	[3,6,8]	0
(1,0)	[0,7,10]	[3,6,8]	3
(1,1)	[0,4,10]	[0,6,8]	4
(1,2)	[0,0,10]	[0,2,8]	0
(2,0)	[0,0,10]	[0,2,8]	0
(2,1)	[0,0,10]	[0,2,8]	2
(2,2)	[0,0,8]	[0,0,8]	8

Final matrix:

[[5,0,0],
 [3,4,0],
 [0,2,8]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every cell is processed exactly once
Space	O(m × n)	The output matrix requires storage for all cells

The algorithm uses two nested loops over the matrix dimensions. Since each operation inside the loop is constant time, the total runtime is proportional to the number of cells.

The additional space beyond the output matrix itself is constant, since only a few variables are maintained during iteration.

Test Cases

from typing import List

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        rows = len(rowSum)
        cols = len(colSum)

        matrix = [[0] * cols for _ in range(rows)]

        for i in range(rows):
            for j in range(cols):
                value = min(rowSum[i], colSum[j])

                matrix[i][j] = value

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

        return matrix

def validate(matrix, original_row, original_col):
    assert [sum(row) for row in matrix] == original_row
    assert [
        sum(matrix[i][j] for i in range(len(matrix)))
        for j in range(len(matrix[0]))
    ] == original_col

sol = Solution()

# Example 1
row = [3, 8]
col = [4, 7]
matrix = sol.restoreMatrix(row[:], col[:])
validate(matrix, row, col)

# Example 2
row = [5, 7, 10]
col = [8, 6, 8]
matrix = sol.restoreMatrix(row[:], col[:])
validate(matrix, row, col)

# Single cell matrix
row = [5]
col = [5]
matrix = sol.restoreMatrix(row[:], col[:])
validate(matrix, row, col)

# Row with zero sum
row = [0, 5]
col = [2, 3]
matrix = sol.restoreMatrix(row[:], col[:])
validate(matrix, row, col)

# Column with zero sum
row = [4, 1]
col = [0, 5]
matrix = sol.restoreMatrix(row[:], col[:])
validate(matrix, row, col)

# All zeros
row = [0, 0]
col = [0, 0]
matrix = sol.restoreMatrix(row[:], col[:])
validate(matrix, row, col)

# Larger rectangular matrix
row = [7, 9, 5]
col = [8, 6, 7]
matrix = sol.restoreMatrix(row[:], col[:])
validate(matrix, row, col)

# Large values
row = [10**8, 10**8]
col = [10**8, 10**8]
matrix = sol.restoreMatrix(row[:], col[:])
validate(matrix, row, col)

Test Summary

Test	Why
[3,8], [4,7]	Validates basic functionality
[5,7,10], [8,6,8]	Tests larger square matrix
Single cell matrix	Smallest possible dimensions
Row containing zero	Ensures zero rows handled correctly
Column containing zero	Ensures zero columns handled correctly
All zeros	Confirms no invalid assignments occur
Rectangular matrix	Tests non-square dimensions
Large values	Verifies handling of large sums

Edge Cases

Rows or Columns with Zero Sum

A row or column may require a total sum of zero. This can easily cause bugs if the implementation assumes every row or column receives positive values.

For example:

rowSum = [0, 5]
colSum = [2, 3]

The first row must contain only zeros.

The greedy solution naturally handles this because:

min(0, colSum[j]) = 0

No invalid positive assignment is ever made.

Single Row or Single Column

If the matrix has only one row or one column, the entire distribution must fit linearly.

Example:

rowSum = [10]
colSum = [3, 4, 3]

The algorithm still works because each step greedily fills as much as possible while respecting remaining sums.

No special handling is required.

Very Large Values

The constraints allow values as large as 10^8.

A poor implementation might use inefficient repeated operations or overflow smaller integer types.

This solution performs only subtraction and minimum comparisons, both of which are safe and efficient. Python integers automatically expand as needed, and Go integers safely support these values under standard constraints.