Find Valid Matrix Given Row and Column Sums

Find Valid Matrix Given Row and Column Sums

1. What is this problem about?

The Find Valid Matrix Given Row and Column Sums interview question is a construction challenge. You are given two arrays representing the desired sums for each row and each column of a matrix. You need to build any matrix of non-negative integers that satisfies these sum requirements. A valid solution is always guaranteed to exist.

2. Why is this asked in interviews?

Companies like Google and Squarepoint Capital ask the Find Valid Matrix coding problem to test a candidate's understanding of Greedy interview patterns. It evaluations whether you can identify a simple, repetitive strategy to satisfy constraints without needing complex backtracking or linear programming. It's a test of "constructive algorithm" design.

3. Algorithmic pattern used

This problem is solved using a Greedy Construction pattern.

1. Iterate: Move through the matrix cell by cell (usually starting at (0, 0)).
2. Greedy Choice: For cell (i, j), assign the maximum possible value that doesn't violate either the current row sum or column sum: val = min(rowSum[i], colSum[j]).
3. Update Constraints: Subtract val from both rowSum[i] and colSum[j].
4. Repeat: Move to the next cell. By taking the minimum, you ensure that at least one of the two constraints (row or column) is satisfied (reaches 0) at each step.

4. Example explanation

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

• Cell (0, 0): min(3, 4) = 3. rowSum[0] becomes 0, colSum[0] becomes 1.
• Cell (0, 1): min(0, 7) = 0.
• Cell (1, 0): min(8, 1) = 1. rowSum[1] becomes 7, colSum[0] becomes 0.
• Cell (1, 1): min(7, 7) = 7. Result Matrix:

3 0
1 7

5. Common mistakes candidates make

• Over-thinking: Trying to distribute the sums evenly or using complex math. The greedy "min" approach is sufficient and much simpler.
• Negative Values: Forgetting that all matrix elements must be non-negative.
• Inefficiency: Not updating the sum arrays as you go, which can lead to invalid matrices.

6. Interview preparation tip

In "construction" problems where any valid answer is accepted, always try the most "local" greedy strategy first. If you can satisfy one constraint at a time without breaking others, you've likely found the intended solution.