
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:
- Initialize the matrix of size
rowSum.length x colSum.length
with all zeros. - 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 andcolSum
for that column. This choice ensures that neither row nor column sum constraints are violated. - Subtract the allocated number simultaneously from the corresponding
rowSum
andcolSum
values, indicating that a portion of the total required sum has been fulfilled.
- This procedure effectively "uses up" the sum constraints in a top-down and left-to-right approach, ensuring all constraints are met.
- Continue the process until all entries in both
rowSum
andcolSum
are zero, implying that a valid matrix formation has been achieved. - 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
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 ofrowSum
andcolSum
inputs respectively. - A 2D matrix
matrix
is then constructed initialized with zeros, created with dimensions based onrows
andcols
. - Two indices,
rowIdx
andcolIdx
, 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 currentrowIdx
andcolIdx
:- 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]
andcolSum[colIdx]
.
- Conditional control then either increments
rowIdx
orcolIdx
, based on whether the current row's total has been fully matched (ifrowSum[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.
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
andcolumnTotals
. - 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 andc
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 betweenrowTotals[r]
andcolumnTotals[c]
. - Decrease the values
rowTotals[r]
andcolumnTotals[c]
by the previously assigned value to adjust the sums. - If the updated
rowTotals[r]
becomes zero, increment the row indexr
; otherwise, increment the column indexc
.
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
.
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:
- Place the smaller value between the current row's sum and the column's sum in the intersecting cell of the matrix.
- Deduct this value from both the corresponding row and column total.
- 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.
No comments yet.