⚡Flashcard Drill➔
NeetCode #811LC-1605MediumGreedy
← Back to All Problems

#811 · #1605 · Find Valid Matrix Given Row and Column Sums(给定行和列的和求可行矩阵)

📌 Problem Statement & Constraints

You are given two arrays rowSum (length m) and colSum (length n). Construct an m x n matrix of non-negative integers whose row sums equal rowSum and whose column sums equal colSum. It is guaranteed that at least one such matrix exists. Return any valid matrix. Constraints: 1 <= m, n <= 500, 0 <= rowSum[i], colSum[j] <= 10^8.

💡 Core Algorithmic Approaches

  1. Fill the matrix greedily cell by cell in row-major order, setting matrix[i][j] = min(rowSum[i], colSum[j]).
  2. Subtract the placed value from both rowSum[i] and colSum[j].
  3. At least one of the two becomes zero, so either the row is finished or the column is finished.
  4. This is correct because the remaining totals always stay non-negative and the guarantee of feasibility means no cell is ever forced negative.

💻 Benchmark Python3 Implementation

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        m, n = len(rowSum), len(colSum)
        res = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                v = min(rowSum[i], colSum[j])   # saturate the smaller total
                res[i][j] = v
                rowSum[i] -= v
                colSum[j] -= v
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): every cell is visited exactly once.
💾 Space Complexity
O(m * n) for the returned matrix (the algorithm itself uses O(1) extra).

⚠️ Interview Pitfalls & Follow-ups

  • Trying to distribute proportionally: a proportional split can create fractions and does not respect the guarantee; the min-rule is exact and integral.
  • Reusing the original arrays elsewhere: rowSum and colSum are mutated in place, which is fine here but surprising if the caller still needs them.
  • Worrying about negatives: the feasibility guarantee plus the min-rule means each subtraction is non-negative; a negative remainder would indicate an infeasible input.
  • Skipping cells where both totals are zero: leaving them at 0 is correct and costs nothing.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems