Find Valid Matrix Given Row and Column Sums

Updated on 29 May, 2025
Find Valid Matrix Given Row and Column Sums header image

Problem Statement

In this problem, you are presented with two arrays: rowSum and colSum. Each of these arrays contains non-negative integers, where each entry rowSum[i] corresponds to the sum of the elements in the i-th row, and each colSum[j] corresponds to the sum of the elements in the j-th column of a theoretical 2D matrix. The task at hand is to construct any 2D matrix that matches these given row and column sums, using non-negative integers. This matrix must be of dimensions equal to the length of rowSum by the length of colSum. The requirement is to return a matrix such that each row and column sum up to the values specified in rowSum and colSum respectively. Importantly, the problem guarantees that at least one valid matrix configuration exists that satisfies the given conditions.

Examples

Example 1

Input:

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

Output:

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

Explanation:

0th row: 3 + 0 = 3 == rowSum[0]
1st row: 1 + 7 = 8 == rowSum[1]
0th column: 3 + 1 = 4 == colSum[0]
1st column: 0 + 7 = 7 == colSum[1]
The row and column sums match, and all matrix elements are non-negative.
Another possible matrix is: [[1,2],
[3,5]]

Example 2

Input:

rowSum = [5,7,10], colSum = [8,6,8]

Output:

[[0,5,0],
[6,1,0],
[2,0,8]]

Constraints

  • 1 <= rowSum.length, colSum.length <= 500
  • 0 <= rowSum[i], colSum[i] <= 108
  • sum(rowSum) == sum(colSum)

Approach and Intuition

The problem is essentially about distributing the sum values among the matrix elements so that the final sums of both rows and columns align with the provided arrays rowSum and colSum. Here's a general approach to forming such a matrix:

  1. Initialize the matrix of size rowSum.length x colSum.length with all zeros.
  2. Proceed row-by-row, trying to consume the entire rowSum for each respective row:
    • For each row, iterate through each column.
    • Allocate to the matrix cell the minimum of rowSum for that row and colSum for that column. This choice ensures that neither row nor column sum constraints are violated.
    • Subtract the allocated number simultaneously from the corresponding rowSum and colSum values, indicating that a portion of the total required sum has been fulfilled.
  3. This procedure effectively "uses up" the sum constraints in a top-down and left-to-right approach, ensuring all constraints are met.
  4. Continue the process until all entries in both rowSum and colSum are zero, implying that a valid matrix formation has been achieved.
  5. Return the constructed matrix.

This strategy works because through each allocation, it ensures that neither the row nor the column exceed its corresponding sum requirement. At each point, the decrease in rowSum and colSum exactly corresponds to the values placed in the matrix, thus maintaining the integrity of the row and column sums.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    vector<vector<int>> reconstructMatrix(vector<int>& rowSum,
                                          vector<int>& colSum) {
        int rows = rowSum.size();
        int cols = colSum.size();

        vector<vector<int>> matrix(rows, vector<int>(cols, 0));
        int rowIdx = 0, colIdx = 0;

        while (rowIdx < rows && colIdx < cols) {
            matrix[rowIdx][colIdx] = min(rowSum[rowIdx], colSum[colIdx]);

            rowSum[rowIdx] -= matrix[rowIdx][colIdx];
            colSum[colIdx] -= matrix[rowIdx][colIdx];

            rowSum[rowIdx] == 0 ? rowIdx++ : colIdx++;
        }
        return matrix;
    }
};

The provided C++ solution efficiently constructs a matrix that aligns with the given row and column sums. Here's a digestible breakdown of the how this solution operates:

  • The reconstructMatrix function initializes by determining the number of rows and columns using the sizes of rowSum and colSum inputs respectively.
  • A 2D matrix matrix is then constructed initialized with zeros, created with dimensions based on rows and cols.
  • Two indices, rowIdx and colIdx, are used to traverse rows and columns respectively.
  • Inside a looping structure, the minimum value between the current row sum (rowSum[rowIdx]) and column sum (colSum[colIdx]) is determined. This minimum value is then placed at the matrix position defined by the current rowIdx and colIdx:
    • This placement ensures that both the particular row's and column's total sums are adhered to as the algorithm progresses.
    • Once the value is placed, it's subtracted from both rowSum[rowIdx] and colSum[colIdx].
  • Conditional control then either increments rowIdx or colIdx, based on whether the current row's total has been fully matched (if rowSum[rowIdx] becomes zero) or if more values need to be added to this row (thus moving to the next column).
  • The loop continues until either all rows or all columns have been processed.
  • Finally, the populated matrix is returned.

This method is effective in ensuring that the resulting matrix meets both the row and column sum requirements efficiently. The use of minimal extras and strict adherence to the sum requirements at each step guarantees the correct configuration of the matrix.

java
class Solution {

    public int[][] reconstructMatrix(int[] rowTotals, int[] columnTotals) {
        int rows = rowTotals.length;
        int columns = columnTotals.length;

        int[][] matrix = new int[rows][columns];
        int r = 0, c = 0;

        while (r < rows && c < columns) {
            matrix[r][c] = Math.min(rowTotals[r], columnTotals[c]);

            rowTotals[r] -= matrix[r][c];
            columnTotals[c] -= matrix[r][c];

            if (rowTotals[r] == 0) {
                r++;
            } else {
                c++;
            }
        }

        return matrix;
    }
}

This document explains how to reconstruct a matrix given the sums of its rows and columns in Java.

The function reconstructMatrix takes two arrays as input: rowTotals and columnTotals, representing the sum of the matrix rows and the sum of the matrix columns respectively.

  • Initialize the number of rows and columns using the lengths of rowTotals and columnTotals.
  • Create a 2D array matrix with dimensions equal to the number of rows and columns, initialized with zeros.
  • Set up two indices, r for rows and c for columns, starting from zero.

The main part of the function utilizes a while loop which runs until either rows or columns index exceeds its respective total number of rows or columns:

  • Assign the value at matrix position [r][c] using the minimum value between rowTotals[r] and columnTotals[c].
  • Decrease the values rowTotals[r] and columnTotals[c] by the previously assigned value to adjust the sums.
  • If the updated rowTotals[r] becomes zero, increment the row index r; otherwise, increment the column index c.

Finally, the function returns the reconstructed matrix matching the provided row and column totals. This approach ensures that the generated matrix adheres directly to the constraints set by rowTotals and columnTotals.

python
class Solution:
    def reconstructMatrix(self, rowTotals, colTotals):
        numRows = len(rowTotals)
        numCols = len(colTotals)

        result_matrix = [[0] * numCols for _ in range(numRows)]
        row_idx, col_idx = 0, 0

        while row_idx < numRows and col_idx < numCols:
            result_matrix[row_idx][col_idx] = min(rowTotals[row_idx], colTotals[col_idx])

            rowTotals[row_idx] -= result_matrix[row_idx][col_idx]
            colTotals[col_idx] -= result_matrix[row_idx][col_idx]

            if rowTotals[row_idx] == 0:
                row_idx += 1
            else:
                col_idx += 1

        return result_matrix

The Python script provided defines a method to reconstruct a matrix based on specific row and column sums. The method reconstructMatrix utilizes two parameters, rowTotals and colTotals, which represent the desired total sum for each row and column respectively. The solution adopts a greedy approach to populate the matrix iteratively, ensuring the sum constraints for rows and columns are met.

Initialize the result matrix with zeros, setting its dimensions according to the lengths of rowTotals and colTotals. Use two counters, row_idx and col_idx, to navigate through matrix cells in a diagonal fashion. In each step:

  1. Place the smaller value between the current row's sum and the column's sum in the intersecting cell of the matrix.
  2. Deduct this value from both the corresponding row and column total.
  3. Move to the next row if the current row's sum reaches zero, otherwise advance to the next column.

The process continues until either all rows or all columns have been handled, appropriately adjusting the matrix along the way to satisfy the designated sum requirements.

On completing the iterations, the method returns a matrix that matches the given row and column sums, confirming that each constraint is precisely met. This approach effectively addresses the problem using a time-efficient method, providing a potential solution for scenarios that require balancing row and column constraints in matrix structures.

Comments

No comments yet.