Find Valid Matrix Given Row and Column Sums: Greedy Cell-by-Cell Construction

You are given two arrays of non-negative integers, rowSum and colSum, where rowSum[i] is the sum of elements in the i-th row and colSum[j] is the sum of elements in the j-th column of a 2D matrix. Your task is to find any non-negative integer matrix of size rowSum.length x colSum.length that satisfies both the row and column sum constraints.

That is LeetCode 1605: Find Valid Matrix Given Row and Column Sums. The problem guarantees a valid answer exists, and any valid answer is accepted. The trick is recognizing that a simple greedy approach fills the matrix correctly on the first pass, with no backtracking needed.

Why this problem matters

This problem sits at the intersection of greedy algorithms and matrix construction. In interviews, it tests whether you can spot that a locally optimal choice (filling each cell with the largest safe value) leads to a globally valid solution. The same greedy intuition appears in problems involving resource allocation, flow distribution, and scheduling where you split a budget across constraints.

It also reinforces a valuable mental model: when constraints pull in two directions (rows want one thing, columns want another), taking the minimum of the two competing demands is often the right move. You will see this min-of-two-constraints pattern in network flow problems, bipartite matching, and interval scheduling.

The key insight

At each cell (r, c), the maximum value you can safely place is min(rowSum[r], colSum[c]). Placing more would violate either the row constraint or the column constraint. Placing exactly the minimum satisfies one of them completely (driving it to zero) and partially satisfies the other.

After you place this value, subtract it from both rowSum[r] and colSum[c]. One of them drops to zero, which means every remaining cell in that row or column must be zero. This cascading zeroing-out effect is what makes the greedy approach work: each placement eliminates at least one row or column from future consideration, so no conflicts build up.

The solution

def restoreMatrix(rowSum: list[int], colSum: list[int]) -> list[list[int]]:
    m, n = len(rowSum), len(colSum)
    matrix = [[0] * n for _ in range(m)]

    for r in range(m):
        for c in range(n):
            val = min(rowSum[r], colSum[c])
            matrix[r][c] = val
            rowSum[r] -= val
            colSum[c] -= val

    return matrix

The code iterates through each cell in row-major order. At each position, it computes the minimum of the remaining row sum and column sum, places that value, and decrements both sums. By the time the loop finishes, every row sum and column sum has been reduced to zero.

Why does the minimum always work? Consider what happens when you place min(rowSum[r], colSum[c]):

• If rowSum[r] is smaller, the entire remaining row budget goes into this cell, and rowSum[r] becomes zero. Every subsequent cell in this row will get zero, which is fine because the row is already satisfied.
• If colSum[c] is smaller, the entire remaining column budget goes into this cell, and colSum[c] becomes zero. Every subsequent cell in this column will get zero.
• If they are equal, both drop to zero simultaneously.

In every case, at least one constraint is fully resolved. The remaining sums stay non-negative, so no cell ever needs a negative value. The process is self-correcting.

Visual walkthrough

Let's trace through the algorithm with rowSum = [3, 8] and colSum = [4, 7].

Notice how each step either exhausts a row sum or a column sum (or both). By the time we reach the last cell, the remaining row and column sums always agree, so the final value drops both to zero.

Complexity analysis

Time: A single pass through all m * n cells. Each cell does O(1) work (one min, one assignment, two subtractions).

Space: The output matrix itself is O(m * n). If you exclude the output, the algorithm uses O(1) extra space since it modifies rowSum and colSum in place.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

Greedy min-of-two-constraints

The pattern of resolving competing constraints by taking their minimum:

val = min(rowSum[r], colSum[c])
matrix[r][c] = val
rowSum[r] -= val
colSum[c] -= val

This is the same idea behind water pouring problems, task assignment with limited resources, and any scenario where you distribute a quantity subject to two independent upper bounds. The minimum guarantees you never exceed either bound. It appears in problems like distributing candies, assigning tasks to workers with capacity limits, and splitting arrays under sum constraints.

In-place constraint reduction

Instead of planning the entire matrix up front, you reduce the problem size with each decision:

for r in range(m):
    for c in range(n):
        val = min(rowSum[r], colSum[c])
        matrix[r][c] = val
        rowSum[r] -= val
        colSum[c] -= val

After placing a value, you update the constraints so the remaining subproblem is smaller. This "solve and shrink" pattern shows up in greedy interval problems (where you pick an interval and remove overlaps), in coin change (where you pick a denomination and reduce the target), and in matrix problems where each cell placement narrows the possibilities for the rest of the grid.

Edge cases

• Single row or single column: the matrix is just a copy of colSum or rowSum respectively. The greedy approach handles this naturally since min(rowSum[0], colSum[c]) equals colSum[c] when there is only one row.
• All zeros: rowSum and colSum are all zeros. Every cell gets zero. The algorithm produces a zero matrix without any special handling.
• One large value dominates: if one row sum equals the total of all column sums, that row absorbs everything. The greedy process fills it correctly because each min call draws from the column sums until they are exhausted.
• Square matrix with equal sums: works identically. The algorithm does not depend on the matrix being square or rectangular.

From understanding to recall

You have seen why the greedy min-of-two approach works and traced it through an example. The algorithm itself is short, just a nested loop with a min and two subtractions, but the reasoning behind why it is correct is the part that is easy to forget.

The fix is spaced repetition. You practice writing the solution from scratch: declare the matrix, loop through cells, compute the min, place the value, decrement the sums. Do it today, again in two days, again in five. After a few reps, the pattern is automatic. You see "construct a matrix with given row and column sums" and the greedy fill just flows out.

The greedy min-of-two-constraints pattern and the in-place constraint reduction pattern are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning these individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the details stick.

Related posts

• Set Matrix Zeroes - Another matrix problem where careful in-place manipulation is the key to optimal space usage
• Spiral Matrix - A classic matrix traversal that tests your ability to manage boundaries and constraints systematically
• Unique Paths - Grid-based problem solving where understanding the structure of the matrix leads to an elegant solution

CodeBricks breaks Find Valid Matrix into its greedy constraint and iterative reduction building blocks, then drills them independently with spaced repetition. You type the nested loop, the min computation, and the sum decrements from scratch until the pattern is automatic. When a constraint-satisfaction matrix problem shows up in your interview, you do not think about it. You just write it.