Find Valid Matrix Given Row and Column Sums - Video Solutions

Problem Overview: You receive two arrays: rowSum and colSum. The task is to construct any non‑negative matrix where each row adds up to rowSum[i] and each column adds up to colSum[j]. Multiple answers may exist; you only need to return one valid matrix.

Approach 1: Greedy Construction (O(m * n) time, O(1) extra space)

The cleanest solution uses a greedy strategy. Iterate through the matrix cell by cell. At position (i, j), assign the smallest possible value that does not violate the remaining row or column requirements: value = min(rowSum[i], colSum[j]). Place this value in the matrix, then subtract it from both rowSum[i] and colSum[j]. This works because every assignment satisfies both constraints locally while preserving feasibility for the remaining cells.

The key insight: if a row still needs r and a column still needs c, the maximum valid value you can place is min(r, c). Filling that amount never blocks future placements because both totals remain non‑negative. Continue iterating across columns for each row until all sums become zero. This approach leverages simple arithmetic and works efficiently with standard array traversal.

Since each cell is visited once, the time complexity is O(m * n), where m is the number of rows and n is the number of columns. Only the output matrix is stored, so auxiliary space remains O(1). This pattern is a classic greedy construction on a matrix.

Approach 2: Network Flow Formulation (O(V * E) typical)

The problem can also be modeled as a flow network. Create a source node connected to each row node with capacity rowSum[i]. Connect each column node to a sink with capacity colSum[j]. Add edges from every row node to every column node with infinite capacity. Running a max‑flow algorithm distributes flow values that correspond to the matrix entries.

This formulation guarantees correctness because flow conservation ensures row and column totals match the required sums. However, it introduces unnecessary overhead compared to the greedy construction. Implementations using Dinic or Edmonds‑Karp are significantly heavier and slower for typical constraints.

Recommended for interviews: The greedy approach is the expected answer. It shows you recognize that each cell can safely take min(rowSum[i], colSum[j]) without violating global constraints. Mentioning the flow interpretation demonstrates deeper understanding, but implementing the greedy solution quickly signals strong problem‑solving instincts.