You are given two arrays rowSum and colSum of non-negative integers where rowSum[i] is the sum of the elements in the ith row and colSum[j] is the sum of the elements of the jth column of a 2D matrix. In other words, you do not know the elements of the matrix, but you do know the sums of each row and column.
Find any matrix of non-negative integers of size rowSum.length x colSum.length that satisfies the rowSum and colSum requirements.
Return a 2D array representing any matrix that fulfills the requirements. It's guaranteed that at least one matrix that fulfills the requirements exists.
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 <= 5000 <= rowSum[i], colSum[i] <= 108sum(rowSum) == sum(colSum)The greedy approach involves iterating over the matrix and at each cell (i, j), filling it with the minimum of the current rowSum[i] and colSum[j]. This method works because as we fill the matrix, we can always satisfy both the row and column conditions by subtracting the filled value from each.
Move through the matrix, adjusting row and column sums at each step. This continues until we've filled the entire matrix, ensuring the integrity of both row and column sum conditions.
This solution creates a matrix with dimensions based on the rowSum and colSum lists. It iteratively assigns to each cell matrix[i][j] the minimum of current rowSum[i] and colSum[j], ensuring non-negativity and consistency with both row and column requirements. The indices i and j are incremented appropriately to iterate through all cells.
C++
Java
C
C#
JavaScript
Time Complexity: O(m + n), where m and n are the lengths of rowSum and colSum respectively, as we're adjusting values once per index.
Space Complexity: O(m * n) for storing the matrix.
Find Valid Matrix Given Row and Column Sums - Leetcode 1605 - Python • NeetCodeIO • 10,481 views views
Watch 9 more video solutions →Practice Find Valid Matrix Given Row and Column Sums with our built-in code editor and test cases.
Practice on FleetCode