Last Updated: 12 Apr, 2021
Find Valid Matrix
Moderate
Asked in company
Ninja has two arrays, ‘rowSum’ and ‘colSum’ of size ‘n’ and ‘m’. Ninja wants to find a matrix of size ‘n’ * ‘m’ such that rowSum[ i ] is equal to the sum of elements of ith row of the matrix for all i from 1 to n and colSum[ j ] is equal to the sum of elements of jth column of the matrix for all j from 1 to m.
Help the Ninja in finding out the matrix. It is guaranteed that solution will exist for the given input.
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line consists of two integer ‘n’ and ‘m’ denoting the size of rowSum array and colSum array.
The next line contains ‘n’ space-separated integers denoting the elements of ‘rowSum’.
The next line contains ‘m’ space-separated integers denoting the elements of ‘colSum’.
Output Format :
Return the valid matrix. There can be many possible solutions, return any of them.
If the returned matrix is valid matrix, the checker will return true else will return false
Constraints :
1 <= ’T’ <= 10
1 <= ‘n’<= 5000
1 <= arr[i][0] ,arrr[i][1] <= 10^6
Where ‘i’ varies from 1 to ‘n’ - 1 where ‘n’ is the length of the array ‘nums’.
Time Limit: 1 sec
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Approaches
The Matrix[i][j] is equal to min(rowSum[i],colSum[j]) and then update rowSum[i] and colSum[ j ] such that rowSum[i]-=Matrix[i][j] and colSum[j]-=Matrix[i][j].In this way it is guaranteed that it will make a valid matrix and satisfy the above conditions.
Algorithm:-
- Create matrix ‘ans’ of size ‘n’ * ‘m’.
- Run a loop from i = 0 to ‘n’.Run a nested loop from j = 0 to ‘m’.
- ans[i][j] = min(rowSum[i], colSum[j]).Then update the rowSum[i] and colSum[j] such that rowSum[i] -= ans[i][j] and colSum[j] -= ans[i][j].
- In the end, return the ‘ans’ matrix.
In Approach1 instead of iterating all values matrix we can iterate only through rowSums and colSums values such that if rowSum[ i ] equal to zero then move to next element similarly in colSum and default values of ‘ans’ matrix will be 0. In this way, it is guaranteed that it will make a valid matrix and satisfy the above conditions.
Algorithm:-
- Create matrix ‘ans’ of size ‘n’ * ‘m’ with default value 0.
- Create two-variable i and j with the default value 0.
- Run a while loop until i < n and j <m.
- ans[i][j] = min(rowSum[i], colSum[j]).Then update the rowSum[i] and colSum[j] such that rowSum[i] -= ans[i][j] and colSum[j] -= ans[i][j].
- if(rowSum[i] == 0) then do i++.
- if(colSum[j] == 0) then do j++.
- Return the ‘ans’ matrix.