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
- Fill the matrix greedily cell by cell in row-major order, setting
matrix[i][j] = min(rowSum[i], colSum[j]). - Subtract the placed value from both
rowSum[i]andcolSum[j]. - At least one of the two becomes zero, so either the row is finished or the column is finished.
- 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:
rowSumandcolSumare 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.