Problem Description

You need to reconstruct a 2D matrix given only the sum of each row and the sum of each column.

You are given:

• rowSum: an array where rowSum[i] represents the sum of all elements in the i-th row of the matrix
• colSum: an array where colSum[j] represents the sum of all elements in the j-th column of the matrix

Your task is to find any valid matrix of non-negative integers with dimensions rowSum.length × colSum.length that satisfies both constraints:

• The sum of elements in each row i equals rowSum[i]
• The sum of elements in each column j equals colSum[j]

The problem guarantees that at least one valid solution exists. You can return any matrix that meets these requirements.

For example, if rowSum = [3, 8] and colSum = [4, 7], one possible valid matrix would be:

[[3, 0],
 [1, 7]]

where row 0 sums to 3, row 1 sums to 8, column 0 sums to 4, and column 1 sums to 7.

Intuition

The key insight is that we can build the matrix greedily by filling each cell with the maximum possible value without violating the constraints.

Think of it this way: at each position (i, j), we need to place a value that contributes to both rowSum[i] and colSum[j]. The maximum value we can place is min(rowSum[i], colSum[j]) - we can't exceed what's left in either the row sum or column sum.

Why does this greedy approach work? Consider what happens when we place x = min(rowSum[i], colSum[j]) at position (i, j):

• If rowSum[i] ≤ colSum[j], we completely satisfy the remaining requirement for row i and partially fulfill column j
• If colSum[j] < rowSum[i], we completely satisfy the remaining requirement for column j and partially fulfill row i

After placing this value, we subtract it from both rowSum[i] and colSum[j] to track the remaining sums needed.

The beauty of this approach is that it guarantees progress - at each step, we're either completing a row's requirement or a column's requirement (or both). Since the total sum of all row sums equals the total sum of all column sums (which the problem guarantees by stating a solution exists), we'll eventually reduce all sums to zero.

By traversing the matrix row by row and applying this greedy strategy at each cell, we systematically construct a valid matrix. The algorithm naturally handles the distribution of values across the matrix without needing complex backtracking or optimization.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a straightforward greedy construction approach:

1. Initialize the answer matrix: Create an m × n matrix filled with zeros, where m = len(rowSum) and n = len(colSum).

2. Iterate through each position: Use nested loops to traverse each cell (i, j) in the matrix from top-left to bottom-right.

3. Apply the greedy strategy: At each position (i, j):

   • Calculate x = min(rowSum[i], colSum[j]) - this is the maximum value we can place without violating constraints
   • Set ans[i][j] = x
   • Update the remaining sums: rowSum[i] -= x and colSum[j] -= x

The algorithm works row by row, filling each position optimally. Let's trace through why this works:

• When we process position (i, j), rowSum[i] represents how much sum is still needed for row i, and colSum[j] represents how much sum is still needed for column j.
• By taking the minimum, we ensure we don't exceed either constraint.
• After processing all n columns in row i, we're guaranteed that rowSum[i] = 0 because the sum of all colSum values initially equals the sum of all rowSum values.
• Similarly, after processing all m rows, each colSum[j] will also reach 0.

The time complexity is O(m × n) since we visit each cell exactly once. The space complexity is O(m × n) for storing the answer matrix.

This greedy approach eliminates the need for backtracking or complex optimization because each local decision (placing the minimum value) leads to a globally valid solution. The algorithm essentially distributes the required sums across the matrix in a way that satisfies both row and column constraints simultaneously.

Example Walkthrough

Let's walk through the algorithm with rowSum = [5, 7] and colSum = [4, 2, 6].

We need to create a 2×3 matrix where:

• Row 0 sums to 5, Row 1 sums to 7
• Column 0 sums to 4, Column 1 sums to 2, Column 2 sums to 6

Initial Setup:

• Create a 2×3 matrix filled with zeros
• Working arrays: rowSum = [5, 7], colSum = [4, 2, 6]

Step-by-step Construction:

Position (0,0):

• min(rowSum[0], colSum[0]) = min(5, 4) = 4
• Place 4 at position (0,0)
• Update: rowSum[0] = 5-4 = 1, colSum[0] = 4-4 = 0
• Matrix: [[4, _, _], [_, _, _]]

Position (0,1):

• min(rowSum[0], colSum[1]) = min(1, 2) = 1
• Place 1 at position (0,1)
• Update: rowSum[0] = 1-1 = 0, colSum[1] = 2-1 = 1
• Matrix: [[4, 1, _], [_, _, _]]

Position (0,2):

• min(rowSum[0], colSum[2]) = min(0, 6) = 0
• Place 0 at position (0,2)
• Update: rowSum[0] = 0, colSum[2] = 6
• Matrix: [[4, 1, 0], [_, _, _]]

Note: Row 0 is now complete with sum = 4+1+0 = 5 ✓

Position (1,0):

• min(rowSum[1], colSum[0]) = min(7, 0) = 0
• Place 0 at position (1,0)
• Update: rowSum[1] = 7, colSum[0] = 0
• Matrix: [[4, 1, 0], [0, _, _]]

Position (1,1):

• min(rowSum[1], colSum[1]) = min(7, 1) = 1
• Place 1 at position (1,1)
• Update: rowSum[1] = 7-1 = 6, colSum[1] = 1-1 = 0
• Matrix: [[4, 1, 0], [0, 1, _]]

Position (1,2):

• min(rowSum[1], colSum[2]) = min(6, 6) = 6
• Place 6 at position (1,2)
• Update: rowSum[1] = 6-6 = 0, colSum[2] = 6-6 = 0
• Matrix: [[4, 1, 0], [0, 1, 6]]

Final Result:

[[4, 1, 0],
 [0, 1, 6]]

Verification:

• Row sums: 4+1+0 = 5 ✓, 0+1+6 = 7 ✓
• Column sums: 4+0 = 4 ✓, 1+1 = 2 ✓, 0+6 = 6 ✓

The greedy approach successfully constructs a valid matrix by always placing the maximum allowable value at each position, ensuring we never violate the row or column sum constraints.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm uses two nested loops. The outer loop iterates m times (number of rows), and the inner loop iterates n times (number of columns). Inside the nested loops, all operations (finding minimum, assignment, and subtraction) are performed in constant time O(1). Therefore, the overall time complexity is O(m × n).

Space Complexity: O(m × n)

The algorithm creates a 2D matrix ans with dimensions m × n to store the result. This matrix requires O(m × n) space. The input arrays rowSum and colSum are modified in-place and don't contribute additional space complexity beyond the input. No other significant auxiliary space is used. Therefore, the space complexity is O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying Input Arrays In-Place

The most significant pitfall in this solution is that it modifies the input arrays rowSum and colSum directly. This can cause issues if:

• The caller expects the original arrays to remain unchanged
• The function needs to be called multiple times with the same input
• The input arrays are used elsewhere in the program after this function call

Example of the problem:

row_sums = [3, 8]
col_sums = [4, 7]
matrix = solution.restoreMatrix(row_sums, col_sums)
# After execution: row_sums = [0, 0], col_sums = [0, 0]
# Original values are lost!

Solution: Create copies of the input arrays before modifying them:

def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
    num_rows, num_cols = len(rowSum), len(colSum)
    result_matrix = [[0] * num_cols for _ in range(num_rows)]
  
    # Create copies to avoid modifying original arrays
    row_remaining = rowSum.copy()
    col_remaining = colSum.copy()
  
    for row_idx in range(num_rows):
        for col_idx in range(num_cols):
            value_to_place = min(row_remaining[row_idx], col_remaining[col_idx])
            result_matrix[row_idx][col_idx] = value_to_place
            row_remaining[row_idx] -= value_to_place
            col_remaining[col_idx] -= value_to_place
  
    return result_matrix

2. Not Validating Input Consistency

While the problem guarantees valid input, in real-world scenarios, the sum of all row sums must equal the sum of all column sums for a valid solution to exist. Not checking this can lead to incorrect results or infinite loops in modified implementations.

Solution: Add validation if needed:

def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
    # Optional validation for production code
    if sum(rowSum) != sum(colSum):
        raise ValueError("No valid matrix exists: row sum total != column sum total")
  
    # Rest of the implementation...

3. Assuming the Greedy Approach Always Works

While the greedy approach works perfectly for this problem, developers might incorrectly assume it works for all matrix reconstruction problems. Some variations (like requiring specific patterns or additional constraints) might need different approaches like backtracking or dynamic programming.

Key insight: The greedy approach works here because we only need to satisfy sum constraints with non-negative integers. Each local optimal choice (minimum value) guarantees progress toward a valid global solution without creating conflicts.