Given two arrays A[] and B[] of N and M integers respectively. Also given is a N X M binary matrix where 1 indicates that there was a positive integer in the original matrix and 0 indicates that the position is filled with 0 in the original matrix. The task is to form back the original matrix such that A[i] indicates the largest element in the ith row and B[j] indicates the largest element in the jth column.
Examples:
Input: A[] = {2, 1, 3}, B[] = {2, 3, 0, 0, 2, 0, 1},
matrix[] = {{1, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 1},
{1, 1, 0, 0, 0, 0, 0}}
Output:
2 0 0 0 2 0 0
0 0 0 0 0 0 1
2 3 0 0 0 0 0
Input: A[] = {2, 4}, B[] = {4, 2},
matrix[] = {{1, 1},
{1, 1}}
Output:
2 2
4 2
Approach: Iterate for every index (i, j) in the matrix, and if mat[i][j] == 1, then fill the position with min(A[i], B[j]). This is because the current element is part of the ith row and the jth column and if the max(A[i], B[j]) was chosen then one of conditions couldn’t be fulfilled i.e. the chosen element could exceed either the maximum element required in the current row or the current column.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
#define N 3
#define M 7
void printOriginalMatrix( int a[], int b[], int mat[N][M])
{
for ( int i = 0; i < N; i++) {
for ( int j = 0; j < M; j++) {
if (mat[i][j] == 1)
cout << min(a[i], b[j]) << " " ;
else
cout << 0 << " " ;
}
cout << endl;
}
}
int main()
{
int a[] = { 2, 1, 3 };
int b[] = { 2, 3, 0, 0, 2, 0, 1 };
int mat[N][M] = { { 1, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1 },
{ 1, 1, 0, 0, 0, 0, 0 } };
printOriginalMatrix(a, b, mat);
return 0;
}
|
Java
class GFG
{
static int N = 3 ;
static int M = 7 ;
static void printOriginalMatrix( int a[], int b[],
int [][] mat)
{
for ( int i = 0 ; i < N; i++)
{
for ( int j = 0 ; j < M; j++)
{
if (mat[i][j] == 1 )
System.out.print(Math.min(a[i],
b[j]) + " " );
else
System.out.print( "0" + " " );
}
System.out.println();
}
}
public static void main(String[] args)
{
int a[] = { 2 , 1 , 3 };
int b[] = { 2 , 3 , 0 , 0 , 2 , 0 , 1 };
int [][] mat = {{ 1 , 0 , 0 , 0 , 1 , 0 , 0 },
{ 0 , 0 , 0 , 0 , 0 , 0 , 1 },
{ 1 , 1 , 0 , 0 , 0 , 0 , 0 }};
printOriginalMatrix(a, b, mat);
}
}
|
Python3
N = 3
M = 7
def printOriginalMatrix(a, b, mat) :
for i in range (N) :
for j in range (M) :
if (mat[i][j] = = 1 ) :
print ( min (a[i], b[j]), end = " " );
else :
print ( 0 , end = " " );
print ()
if __name__ = = "__main__" :
a = [ 2 , 1 , 3 ]
b = [ 2 , 3 , 0 , 0 , 2 , 0 , 1 ]
mat = [[ 1 , 0 , 0 , 0 , 1 , 0 , 0 ],
[ 0 , 0 , 0 , 0 , 0 , 0 , 1 ],
[ 1 , 1 , 0 , 0 , 0 , 0 , 0 ]];
printOriginalMatrix(a, b, mat);
|
C#
using System;
class GFG
{
static int N = 3;
static int M = 7;
static void printOriginalMatrix( int [] a, int [] b,
int [,] mat)
{
for ( int i = 0; i < N; i++)
{
for ( int j = 0; j < M; j++)
{
if (mat[i,j] == 1)
Console.Write(Math.Min(a[i],
b[j]) + " " );
else
Console.Write( "0" + " " );
}
Console.WriteLine();
}
}
public static void Main()
{
int [] a = { 2, 1, 3 };
int [] b = { 2, 3, 0, 0, 2, 0, 1 };
int [,] mat = {{ 1, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1 },
{ 1, 1, 0, 0, 0, 0, 0 }};
printOriginalMatrix(a, b, mat);
}
}
|
PHP
<?php
$N = 3;
$M = 7;
function printOriginalMatrix( $a , $b , $mat )
{
for ( $i = 0; $i < $GLOBALS [ 'N' ]; $i ++)
{
for ( $j = 0; $j < $GLOBALS [ 'M' ]; $j ++)
{
if ( $mat [ $i ][ $j ] == 1)
echo min( $a [ $i ], $b [ $j ]). " " ;
else
echo "0" . " " ;
}
echo "\r\n" ;
}
}
$a = array ( 2, 1, 3 );
$b = array (2, 3, 0, 0, 2, 0, 1 );
$mat = array ( array ( 1, 0, 0, 0, 1, 0, 0 ),
array ( 0, 0, 0, 0, 0, 0, 1 ),
array ( 1, 1, 0, 0, 0, 0, 0 ));
printOriginalMatrix( $a , $b , $mat );
?>
|
Javascript
<script>
let N = 3;
let M = 7;
function printOriginalMatrix(a,b,mat)
{
for (let i = 0; i < N; i++)
{
for (let j = 0; j < M; j++)
{
if (mat[i][j] == 1)
document.write(Math.min(a[i],
b[j]) + " " );
else
document.write( "0" + " " );
}
document.write( "<br>" );
}
}
let a = [ 2, 1, 3 ];
let b = [ 2, 3, 0, 0, 2, 0, 1 ];
let mat = [[ 1, 0, 0, 0, 1, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 1 ],
[ 1, 1, 0, 0, 0, 0, 0 ]];
printOriginalMatrix(a, b, mat);
</script>
|
Output:
2 0 0 0 2 0 0
0 0 0 0 0 0 1
2 3 0 0 0 0 0
Time Complexity: O(N * M)
Auxiliary Space: O(1)