Leetcode 1605. Find Valid Matrix Given Row and Column Sums

Problem Explanation

Let's start with rowSum and colSum. These are arrays that give us the sums of the rows and columns of a particular matrix. However, we are not given the matrix itself. Instead, we are asked to reconstruct the matrix based on rowSum and colSum.

In other words, we know that the sum of the elements in the ith row is rowSum[i] and the sum of the jth column is colSum[j] in the matrix. Our task is to generate any matrix that fulfills these sum requirements.

Note that there may be multiple valid matrices that fulfill the sum requirements. Hence, the function does not require a unique solution.

Let's explain with an example:

---

Example: rowSum = [3,8], colSum = [4,7] The output can be: ([[3,0],[1,7]]) or ([[1,2],[3,5]])

We know that the sum of elements in the row marked by 'ith' index for rowSum is equal to rowSum[i], so for rowSum[0] = 3 the sum of elements in the row0 results in 3. And rowSum[1] = 8 gives the sum of elements in row1 is equal to 8. Similarly for column-wise check colSum[0] = 4 and colSum[1] = 7, the sum of elements in column0 and column1 are equal to 4 & 7 respectively. This condition is satisfied by both ([[3,0],[1,7]]) and ([[1,2],[3,5]]).

---

Solution approach

The solution approach is based on greedy algorithm mechanism. We iterate over each cell of the expected matrix. Now for the cell at row 'i' and column 'j', we know that the value of the cell cannot exceed rowSum[i] (if it goes beyond, then sum of row 'i' cannot be rowSum[i]) and colSum[j] (for similar reasons). Therefore, the cell value is the minimum of these two. This is what greedy approach mandates.

We subtract this value from both rowSum[i] and colSum[j] (since we have used this amount). Iterating this over each cell, gives us the desired matrix.

Solutions

Python

1
2python
3class Solution:
4    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
5        m, n = len(rowSum), len(colSum)
6        ans = [[0]*n for _ in range(m)]
7        
8        for i in range(m):
9            for j in range(n):
10                ans[i][j] = min(rowSum[i], colSum[j])
11                rowSum[i] -= ans[i][j]
12                colSum[j] -= ans[i][j]
13        
14        return ans

Java

1
2java
3public class Solution {
4    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
5        int m = rowSum.length, n = colSum.length;
6        int[][] ans = new int[m][n];
7        
8        for (int i = 0; i < m; ++i)
9            for (int j = 0; j < n; ++j) {
10                ans[i][j] = Math.min(rowSum[i], colSum[j]);
11                rowSum[i] -= ans[i][j];
12                colSum[j] -= ans[i][j];
13            }
14        return ans;
15    }
16}

Javascript

1
2javascript
3class Solution {
4    restoreMatrix(rowSum, colSum) {
5        const m = rowSum.length, n = colSum.length;
6        const ans = Array.from({length: m}, () => Array(n).fill(0));
7        
8        for (let i = 0; i < m; ++i)
9            for (let j = 0; j < n; ++j) {
10                ans[i][j] = Math.min(rowSum[i], colSum[j]);
11                rowSum[i] -= ans[i][j];
12                colSum[j] -= ans[i][j];
13    }
14        return ans;
15    }
16}

C++

1
2cpp
3class Solution {
4public:
5    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
6        int m = rowSum.size(), n = colSum.size();
7        vector<vector<int>> ans(m, vector<int>(n));
8        
9        for (int i = 0; i < m; ++i)
10            for (int j = 0; j < n; ++j) {
11                ans[i][j] = min(rowSum[i], colSum[j]);
12                rowSum[i] -= ans[i][j];
13                colSum[j] -= ans[i][j];
14            }
15        return ans;
16    }
17};

C#

1
2csharp
3public class Solution {
4    public int[][] RestoreMatrix(int[] rowSum, int[] colSum) {
5        int m = rowSum.Length, n = colSum.Length;
6        int[][] ans = new int[m][];
7        for(int i=0; i<m; i++)  ans[i] = new int[n];
8        
9        for (int i = 0; i < m; ++i)
10            for (int j = 0; j < n; ++j) {
11                ans[i][j] = Math.Min(rowSum[i], colSum[j]);
12                rowSum[i] -= ans[i][j];
13                colSum[j] -= ans[i][j];
14            }
15        return ans;
16    }
17}

In each of these functions, we generate an empty matrix of the correct size, iterate over it, and greedily assign each cell as described before. After filling the value to the current cell, we subtract the allocated number from the corresponding row's sum and column's sum to get the new target sums for rest of the cells.

Thus, the code correctly fills up the matrix one cell at a time, adjusting the row and column sums as it goes along, ensuring at all times that the row and column indices are in balance.## Complexity Analysis

The time complexity of the above algorithm is O(m*n), where m is the number of rows and n is the number of columns. We compute the value of each cell exactly once, therefore the time complexity is directly proportional to the size of the matrix.

The space complexity is also O(mn), as we need to create and return a matrix of size m rows and n columns. Additionally, the space needed for the input row and column sum arrays are O(m) and O(n) respectively. Therefore, the total space complexity is O(m+n) for input and O(mn) for output.

Regardless of the implementation language, the time and space complexity remains the same.

A key point to note here is that this problem does not have unique solutions. As long as the computed matrix meets the row and column sums condition, it can be considered as a valid solution. So, different implementations might yield different valid outputs.

Conclusion

This problem is an intriguing example of the application of Greedy algorithms. The decisions are made locally at each cell to ensure the global sum conditions are not violated. Despite having no unique solutions, the algorithms in Python, Java, JavaScript, C++ and C# successfully reconstruct a matrix that satisfies the requirements. Learning to implement such solutions can significantly improve your problem-solving skills. Furthermore, understanding how to apply the greedy choice property and optimal substructure in a problem is crucial for tackling a wide range of complex issues, especially in real-world applications.