Check matrix transformation by flipping sub-matrices along the principal or anti-diagonal
Given two matrices mat1[][] and mat2[][] of size N*M, the task is check if it is possible to transform mat1 into mat2 by selecting any square sub-matrix from mat1 and flipping it along its principal diagonal or anti-diagonal.
Examples:
Input: N = 2, M = 3, mat1[][] = {{1, 2, 3}, {4, 5, 6}}, mat2[][] = {{1, 4, 3}, {6, 5, 2}}
Output: YES
Explanation:Input: N = 3, M = 3, mat1[][] = {{12, 11, 8}, {7, 1, 1}, {9, 2, 4}}, mat2[][] = {{4, 1, 8}, {2, 1, 11}, {9, 7, 15}}
Output: NO
Explanation: It can be verified that it is not possible to make all mat1[][] equal to mat2[][].
Approach:
The problem is observation based. If we assume the matrix as a chessboard and then map the color (Black & White) with elements. Then it is possible to place the element having black cell at any cell of whole matrix which have black cell using given operation. Same with the white cell elements. So, according to this observation, conversion from matrix mat1 to mat2 will be possible only and only if, the same element present at same colored cell in both matrices. Therefore, we will follow the below approach to solve the problem:
- Create 4 HashSets having name as B1, W1, B2, W2. Where:
- B1 will store the elements placed at black cells in matrix mat1[][].
- W1 will store the elements placed at white cells in matrix mat1[][].
- B2 will store the elements placed at black cells in matrix mat2[][].
- W2 will store the elements placed at white cells in matrix mat2[][].
After that conversion from mat1 to mat2 will be possible only and only if (B1 == B2 && W1 == W2).
For implementing the approach, the element at position (i, j) such that ((i + j) % 2 == 0) is assumed to place on Black cell for all (1 <= i <= N) and (1 <= j <= M).
Steps-by-step approach:
- If there is only 1 row or 1 column in mat1[][] and mat2[][]. Then check manually for equality of elements and output YES/NO by same.
- Otherwise,
- Create 4 HashSets as B1, B2, W1, W2.
- Run two nested loops from i= 0 to i < N and j = 0 to j < M and follow below mentioned steps under the scope of inner loop:
- If ((i+j) % 2 == 0)
- B1.add(A[i][j])
- B2.add(B[i][j])
- Else
- W1.add(A[i][j])
- W2.add(B[i][j])
- If ((i+j) % 2 == 0)
- If (B1 contains same elements as B2 and W1 contains same elements as W2)
- Output YES
- Otherwise
- Output NO
Below is the implementation of the above approach:
C++
#include <iostream> #include <vector> #include <unordered_set> using namespace std; // Function declarations void Check_Possibility( int N, int M, vector<vector< long long >>& mat1, vector<vector< long long >>& mat2); // Driver Function int main() { // Inputs int N = 2; int M = 3; vector<vector< long long >> mat1 = { { 1, 2, 3 }, { 4, 5, 6 } }; vector<vector< long long >> mat2 = { { 1, 4, 3 }, { 6, 5, 2 } }; // Function call Check_Possibility(N, M, mat1, mat2); return 0; } // Function to check if it is possible to convert mat1[][] as mat2[][] using given operations void Check_Possibility( int N, int M, vector<vector< long long >>& mat1, vector<vector< long long >>& mat2) { // If there is only 1 row or 1 column // Then operations can't be applied because // In such cases square sub-matrix can only be of // size 1*1, In such sub-matrix there will be no // change in place of elements. Thus checking for // equal elements manually. if (N == 1 || M == 1) { // Flag to take a decision to print output as YES // or NO bool flag = true ; // If there is only 1 row in mat1[][] and // mat2[][] Then mat1[0][i] must be equal to // mat2[0][i] for all (0 <= i <= M-1) for YES if (N == 1) { for ( int i = 0; i < M; i++) { if (mat1[0][i] != mat2[0][i]) { flag = false ; break ; } } } // If there is only 1 column in mat1[][] and // mat2[][] else { for ( int i = 0; i < N; i++) { if (mat1[i][0] != mat2[i][0]) { flag = false ; break ; } } } // Printing output on the basis of Boolean Flag cout << (flag ? "YES" : "NO" ) << endl; return ; } // This part will execute when row or col is not // equal to 1 Creating 4 HashSets as discussed in // the approach unordered_set< long long > black1, black2, white1, white2; // Mapping the elements into Sets according to their // color of cell. for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { if ((i + j) % 2 == 0) { black1.insert(mat1[i][j]); black2.insert(mat2[i][j]); } else { white1.insert(mat1[i][j]); white2.insert(mat2[i][j]); } } } // If (Black1 contains the same elements as Black2 && // White1 contains the same elements as White2) // The only conversion from mat1[][] to mat2[][] is possible // Otherwise not if (black1 == black2 && white1 == white2) { cout << "YES" << endl; } else { cout << "NO" << endl; } } |
Java
// Java code to implement the approach import java.util.*; // Driver Class public class Main { // Driver Function public static void main(String[] args) { // Inputs int N = 2 ; int M = 3 ; long [][] mat1 = { { 1 , 2 , 3 }, { 4 , 5 , 6 } }; long [][] mat2 = { { 1 , 4 , 3 }, { 6 , 5 , 2 } }; // Function_call Check_Possibility(N, M, mat1, mat2); } // Function to check if it is possible to convert // mat1[][] as mat2[][] using given operations public static void Check_Possibility( int N, int M, long [][] mat1, long [][] mat2) { // If there is only 1 row or 1 column // Then operations can't be applied because // In such cases square sub-matrix can only be of // size 1*1, In such sub-matrix there will be no // change in place of elements. Thus checking for // equal elements manually. if (N == 1 || M == 1 ) { // Flag to take decision to print output as YES // or NO boolean flag = true ; // If there is only 1 row in mat1[][] and // mat2[][] Then mat1[0][i] must be equal to // mat2[0][i] for all (0 <= i <= M-1) for YES if (N == 1 ) { for ( int i = 0 ; i < M; i++) { if (mat1[ 0 ][i] != mat2[ 0 ][i]) { flag = false ; break ; } } } // If there is only 1 column in mat1[][] and // mat2[][] else { for ( int i = 0 ; i < N; i++) { if (mat1[i][ 0 ] != mat2[i][ 0 ]) { flag = false ; break ; } } } // Printing output on the basis of Boolean Flag System.out.println(flag ? "YES" : "NO" ); return ; } // This part will execute when row or col is not // equal to 1 Creating 4 HashSets as discussed in // approach HashSet<Long> black1 = new HashSet<>(); HashSet<Long> black2 = new HashSet<>(); HashSet<Long> white1 = new HashSet<>(); HashSet<Long> white2 = new HashSet<>(); // Mapping the elements into Sets according to their // color of cell. for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < M; j++) { if ((i + j) % 2 == 0 ) { black1.add(mat1[i][j]); black2.add(mat2[i][j]); } else { white1.add(mat1[i][j]); white2.add(mat2[i][j]); } } } // If (Black1 contains same elements as Black2 && // White1 contains same elements as White2) The only // conversion from mat1[][] to mat2[][] is possible // Otherwise not if (black1.equals(black2) && white1.equals(white2)) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } } |
C#
using System; using System.Collections.Generic; class Program { // Function declarations static void CheckPossibility( int N, int M, List<List< long >> mat1, List<List< long >> mat2) { // If there is only 1 row or 1 column // Then operations can't be applied because // In such cases square sub-matrix can only be of // size 1*1, In such sub-matrix there will be no // change in place of elements. Thus checking for // equal elements manually. if (N == 1 || M == 1) { // Flag to take a decision to print output as YES // or NO bool flag = true ; // If there is only 1 row in mat1[][] and // mat2[][] Then mat1[0][i] must be equal to // mat2[0][i] for all (0 <= i <= M-1) for YES if (N == 1) { for ( int i = 0; i < M; i++) { if (mat1[0][i] != mat2[0][i]) { flag = false ; break ; } } } // If there is only 1 column in mat1[][] and // mat2[][] else { for ( int i = 0; i < N; i++) { if (mat1[i][0] != mat2[i][0]) { flag = false ; break ; } } } // Printing output on the basis of Boolean Flag Console.WriteLine(flag ? "YES" : "NO" ); return ; } // This part will execute when row or col is not // equal to 1 Creating 4 HashSets as discussed in // the approach HashSet< long > black1 = new HashSet< long >(); HashSet< long > black2 = new HashSet< long >(); HashSet< long > white1 = new HashSet< long >(); HashSet< long > white2 = new HashSet< long >(); // Mapping the elements into Sets according to their // color of cell. for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { if ((i + j) % 2 == 0) { black1.Add(mat1[i][j]); black2.Add(mat2[i][j]); } else { white1.Add(mat1[i][j]); white2.Add(mat2[i][j]); } } } // If (Black1 contains the same elements as Black2 && // White1 contains the same elements as White2) // The only conversion from mat1[][] to mat2[][] is possible // Otherwise not if (black1.SetEquals(black2) && white1.SetEquals(white2)) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } // Driver Function static void Main() { // Inputs int N = 2; int M = 3; List<List< long >> mat1 = new List<List< long >> { new List< long > { 1, 2, 3 }, new List< long > { 4, 5, 6 } }; List<List< long >> mat2 = new List<List< long >> { new List< long > { 1, 4, 3 }, new List< long > { 6, 5, 2 } }; // Function call CheckPossibility(N, M, mat1, mat2); } } |
Javascript
// Function to check if it is possible to convert mat1[][] as mat2[][] using given operations function checkPossibility(N, M, mat1, mat2) { // If there is only 1 row or 1 column // Then operations can't be applied because // In such cases square sub-matrix can only be of // size 1*1, In such sub-matrix there will be no // change in place of elements. Thus checking for // equal elements manually. if (N === 1 || M === 1) { // Flag to take a decision to print output as YES // or NO let flag = true ; // If there is only 1 row in mat1[][] and // mat2[][] Then mat1[0][i] must be equal to // mat2[0][i] for all (0 <= i <= M-1) for YES if (N === 1) { for (let i = 0; i < M; i++) { if (mat1[0][i] !== mat2[0][i]) { flag = false ; break ; } } } // If there is only 1 column in mat1[][] and // mat2[][] else { for (let i = 0; i < N; i++) { if (mat1[i][0] !== mat2[i][0]) { flag = false ; break ; } } } // Printing output on the basis of Boolean Flag console.log(flag ? "YES" : "NO" ); return ; } // This part will execute when row or col is not // equal to 1 Creating 4 Sets as discussed in // the approach let black1 = new Set(), black2 = new Set(), white1 = new Set(), white2 = new Set(); // Mapping the elements into Sets according to their // color of cell. for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { if ((i + j) % 2 === 0) { black1.add(mat1[i][j]); black2.add(mat2[i][j]); } else { white1.add(mat1[i][j]); white2.add(mat2[i][j]); } } } // If (Black1 contains the same elements as Black2 && // White1 contains the same elements as White2) // The only conversion from mat1[][] to mat2[][] is possible // Otherwise not if (setEquals(black1, black2) && setEquals(white1, white2)) { console.log( "YES" ); } else { console.log( "NO" ); } } // Function to check if two sets are equal function setEquals(set1, set2) { if (set1.size !== set2.size) return false ; for (let item of set1) { if (!set2.has(item)) return false ; } return true ; } // Inputs let N = 2; let M = 3; let mat1 = [[1, 2, 3], [4, 5, 6]]; let mat2 = [[1, 4, 3], [6, 5, 2]]; // Function call checkPossibility(N, M, mat1, mat2); //This code is contributed by Utkarsh |
Python3
# Function to check if it is possible to convert mat1[][] as mat2[][] using given operations def check_possibility(N, M, mat1, mat2): # If there is only 1 row or 1 column # Then operations can't be applied because # In such cases square sub-matrix can only be of # size 1*1, In such sub-matrix there will be no # change in place of elements. Thus checking for # equal elements manually. if N = = 1 or M = = 1 : # Flag to take a decision to print output as YES # or NO flag = True # If there is only 1 row in mat1[][] and # mat2[][] Then mat1[0][i] must be equal to # mat2[0][i] for all (0 <= i <= M-1) for YES if N = = 1 : for i in range (M): if mat1[ 0 ][i] ! = mat2[ 0 ][i]: flag = False break # If there is only 1 column in mat1[][] and # mat2[][] else : for i in range (N): if mat1[i][ 0 ] ! = mat2[i][ 0 ]: flag = False break # Printing output on the basis of Boolean Flag print ( "YES" if flag else "NO" ) return # This part will execute when row or col is not # equal to 1 Creating 4 HashSets as discussed in # the approach black1, black2, white1, white2 = set (), set (), set (), set () # Mapping the elements into Sets according to their # color of cell. for i in range (N): for j in range (M): if (i + j) % 2 = = 0 : black1.add(mat1[i][j]) black2.add(mat2[i][j]) else : white1.add(mat1[i][j]) white2.add(mat2[i][j]) # If (Black1 contains the same elements as Black2 && # White1 contains the same elements as White2) # The only conversion from mat1[][] to mat2[][] is possible # Otherwise not if black1 = = black2 and white1 = = white2: print ( "YES" ) else : print ( "NO" ) # Driver Function if __name__ = = "__main__" : # Inputs N = 2 M = 3 mat1 = [[ 1 , 2 , 3 ], [ 4 , 5 , 6 ]] mat2 = [[ 1 , 4 , 3 ], [ 6 , 5 , 2 ]] # Function call check_possibility(N, M, mat1, mat2) |
YES
Time Complexity: O(M*N)
Auxiliary Space: O(N), As multiple HashSets are used.