Find Valid Matrix

Moderate

0/80

Average time to solve is 30m

Contributed by

0 upvote

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

Sample Output 1 :

1 2 3
4 5 6
7 8 9

Sample Explanation :

For the matrix given for sample testcase 1:-
The sum of the 1st row = 1 + 2 + 3 = 6 which is equal to rowSum[ 1 ].
The sum of  the 2nd row = 4 + 5 + 6 = 15 which is equal to rowSum[ 2 ].
The sum of the 3rd row = 7 + 8 + 9 = 24 which is equal to rowSum[ 3 ].
The sum of 1st column = 1 + 4 + 7 = 12 which is equal to colSum[ 1 ].
The sum of the 2nd column = 2 + 5 + 8 = 15 which is equal to colSum[ 2 ].
The sum of the 3rd column = 3 + 6 + 9 = 18 which is equal to colSum[ 3 ].

Hence it satisfies the condition and it is a valid matrix.

Sample Input 2 :

Sample Output 2 :

5 6 7
8 11 9

Hint 1

Hint 2

The cell in the ‘i’ th row and ‘j' th column will have the value min(rowSum[i],colSum[j])

Approaches (2)

Approach 1

Approach 2

Brute Force Approach

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.

Time Complexity

O(n*m) where ‘n’ is the size of rowSum array and ‘m’ is the size of colSum array.

We are running a nested loop from 0 to n and from 0 to m.

Space Complexity

O(n*m) where ‘n’ is the size of rowSum array and ‘m’ is the size of colSum array.

We are creating an auxiliary matrix of size n*m.

(100% EXP penalty)

Find Valid Matrix

Console