Find Valid Matrix Given Row and Column Sums

In this article i am going to explain the approach and solution for this leetcode problem

In the given problem we are given with two arrays one is rowSum and other is colSum
basically what they are nothing but arrays of the sum of ith row and jth column of the matrix and we have to find the valid matrix.

So what will be our approach ?

It is simple what we will be doing is taking out maximum valid element possible for that position of matrix by selecting the minimum of that particular position's row and column and then updating that particular position' row and column sum by subtracting the choosen value from both row sum and column sum.
Let's understand by the example rowSum = [5,7,10], colSum = [8,6,8]

Now if either the rowSum[i] or colSum[j] becomes 0 we can say, that particular row or column is locked as the condition for that row is satisfied so we will move our j or i pointer according to that.

And since our rowSum[i] becomes zero we can move our i pointer or row to next

Now for this row we have colSum allowed is 3 and rowSum allowed is 7 hence we will choose min i.e 3 and by putting 3 our colSum[0] will also become 0

We will move our column pointer to the next . and will repeat the same procedure

rowSum[1] becomes zero we move our row pointer to next.

Now here the minimum is 2 hence we choose 2 and subtract it from both rowSum[2] and colSum[1] , after this operation our colSum[1] becomes 0 hence we will move the col pointer.

After moving the pointer to the next column we choose 8 and subtract from both our both rowSum[2] and colSum[2] becomes 0 and also reaches to end hence no further operations.

Here is how our matrix will look for now

Now the remaining another positions will be filled with zero which is the default value.

Now if we have a final look at our matrix our matrix satisfies the condition and is our answer

Now I hope that I was able to explain the approach so here is the code

class Solution {
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int m = rowSum.length;
        int n = colSum.length;
        int i =0;
        int j = 0;
        int[][] mat= new int[m][n];
        while(i<m&&j<n){
            int el = Math.min(rowSum[i],colSum[j]);
            mat[i][j] = el;
            rowSum[i]-=el;
            colSum[j]-=el;
            if(rowSum[i]==0){
                i++;
            }
            if(colSum[j]==0){
                j++;
            }
        }
 return mat;
    }
}

The time complexity of this solution is O(m*n) where m is the number of rows and n is the number of columns in the matrix. This is because we iterate through each element in the matrix once to fill in the values based on the rowSum and colSum arrays. The space complexity is O(m*n) as well, as we are creating a new matrix of size m*n to store the restored matrix values.

Thank you for reading will see you next time bye 🫡