Given two 2D matrices mat[][] and T[][] of size M×N and P×Q respectively. The task is to check whether the matrix T[][] is a result of one or more 90° rotations of the matrix mat[][].
Examples:
Input: mat[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, T[][] ={{7, 4, 1}, {8, 5, 2}, {9, 6, 3}}
Output: Yes
Explanation:
From the figures given above, it is clear that T[][] is obtained by rotating 90° once.
Input: mat[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, T[][] = {{1, 4, 7}, {8, 5, 2}, {9, 6, 3}}
Output: No
Approach: The given problem can be solved based on the following observations:
- Consider the following 2D matrix:
- Rotating it several times by 90° gets the following matrices:
- From the above figures, it can be seen that every row can either occur as it is or in its reversed form.
- The same can be observed for the columns
Hence, if T[][] is one of the rotated forms of mat[][], it must have at least one occurrence of the original or the reversed form of mat[][]’s rows and columns present as its rows and columns.
Follow the steps below to solve the problem:
- If the dimensions of mat[][] and T[][] are not equal or not then print “No” and return.
- Initialize a map of vectors, say m to store the frequencies of all rows, columns, and their reversed versions.
- Iterate in the range [0, M-1] and using the variable i and perform the following steps:
- Increment m[(mat[i])] by 1 and then reverse the vector mat[i] and then increment m[(mat[i])] by 1.
- Iterate in the range [0, N-1] and using the variable i and perform the following steps:
- Push all the elements of the ith column in a vector say r.
- Increment m[r] by 1 and then reverse the vector r and then increment m[r] by 1.
- Iterate in the range [0, M-1] and using the variable i and perform the following steps:
- If m[T[i]] is less than 0 then print “No” and return.
- Otherwise, decrement m[T[i]] by 1.
- Iterate in the range [0, N-1] and using the variable i and perform the following steps:
- Push all the elements of the ith column of T[][] in a vector say r.
- If m[r] is less than 0 then print “No” and return.
- Otherwise, decrement m[r] by 1.
- Finally, if none of the above cases satisfy then print “Yes“.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check whether another// matrix can be created by rotating// mat one or more times by 90 degreesstring findRotation(vector<vector<int> >& mat, vector<vector<int> >& T){ // If the dimensions of both the // arrays don't match if (T.size() != mat.size() || T[0].size() != mat[0].size()) { // Return false return "No"; } // Map to store all rows, columns // and their reversed versions map<vector<int>, int> m; // Iterate in the range [0, M-1] for (int i = 0; i < mat.size(); i++) { // Increment the frequency of the // i'th row by 1 m[(mat[i])] += 1; // Reverse the i'th row reverse(mat[i].begin(), mat[i].end()); // Increment the frequency of the // i'th row by 1 m[(mat[i])] += 1; } // Iterate in the range [0, N-1] for (int i = 0; i < mat[0].size(); i++) { // Stores the i'th column vector<int> r = {}; // Iterate in the range [0, M-1] for (int j = 0; j < mat.size(); j++) { r.push_back(mat[j][i]); } // Increment the frequency of the // i'th column by 1 m[r] += 1; // Reverse the i'th column reverse(r.begin(), r.end()); // Increment the frequency of the // i'th column by 1 m[r] += 1; } // Iterate in the range [0, M-1] for (int i = 0; i < T.size(); i++) { // If frequency of the i'th row // is more in T[][] than in the // mat[][]. if (m[T[i]] <= 0) { return "No"; } // Decrement the frequency of the // i'th row by 1 m[T[i]] -= 1; } // Iterate in the range [0, N-1] for (int i = 0; i < T[0].size(); i++) { // Stores the ith column vector<int> r = {}; // Iterate in the range [0, M-1] for (int j = 0; j < T.size(); j++) { r.push_back(T[j][i]); } // If frequency of the i'th column // is more in T[][] than in mat[][]. if (m[r] <= 0) { return "No"; } // Decrement the frequency of the i'th // column by 1 m[r] -= 1; } // Return "Yes" return "Yes";}// Driver codeint main(){ // Input vector<vector<int> > mat = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; vector<vector<int> > T = { { 3, 6, 9 }, { 2, 5, 8 }, { 1, 4, 7 } }; // Function call cout << findRotation(mat, T); return 0;} |
Java
import java.util.Arrays;import java.util.HashMap;import java.util.Map;public class MatrixRotationCheck { // Function to check whether another matrix can be created by rotating // mat one or more times by 90 degrees public static String findRotation(int[][] mat, int[][] T) { // If the dimensions of both arrays don't match if (T.length != mat.length || T[0].length != mat[0].length) { // Return "No" return "No"; } // Map to store all rows, columns, and their reversed versions Map<String, Integer> m = new HashMap<>(); // Iterate through the matrix for (int[] row : mat) { // Increment the frequency of the row and its reverse by 1 String rowStr = Arrays.toString(row); m.put(rowStr, m.getOrDefault(rowStr, 0) + 1); int[] reversedRow = Arrays.copyOf(row, row.length); for (int i = 0, j = row.length - 1; i < j; i++, j--) { int temp = reversedRow[i]; reversedRow[i] = reversedRow[j]; reversedRow[j] = temp; } String reversedRowStr = Arrays.toString(reversedRow); m.put(reversedRowStr, m.getOrDefault(reversedRowStr, 0) + 1); } // Iterate through the columns of the matrix for (int j = 0; j < mat[0].length; j++) { int[] column = new int[mat.length]; for (int i = 0; i < mat.length; i++) { column[i] = mat[i][j]; } // Increment the frequency of the column and its reverse by 1 String columnStr = Arrays.toString(column); m.put(columnStr, m.getOrDefault(columnStr, 0) + 1); int[] reversedColumn = Arrays.copyOf(column, column.length); for (int i = 0, k = column.length - 1; i < k; i++, k--) { int temp = reversedColumn[i]; reversedColumn[i] = reversedColumn[k]; reversedColumn[k] = temp; } String reversedColumnStr = Arrays.toString(reversedColumn); m.put(reversedColumnStr, m.getOrDefault(reversedColumnStr, 0) + 1); } // Iterate through the target matrix T for (int[] row : T) { // If the frequency of the row is less in T than in mat String rowStr = Arrays.toString(row); if (m.getOrDefault(rowStr, 0) <= 0) { return "No"; } // Decrement the frequency of the row by 1 m.put(rowStr, m.get(rowStr) - 1); } // Iterate through the columns of the target matrix T for (int j = 0; j < T[0].length; j++) { int[] column = new int[T.length]; for (int i = 0; i < T.length; i++) { column[i] = T[i][j]; } // If the frequency of the column is less in T than in mat String columnStr = Arrays.toString(column); if (m.getOrDefault(columnStr, 0) <= 0) { return "No"; } // Decrement the frequency of the column by 1 m.put(columnStr, m.get(columnStr) - 1); } // Return "Yes" return "Yes"; } // Driver code public static void main(String[] args) { // Input matrices int[][] mat = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; int[][] T = { {3, 6, 9}, {2, 5, 8}, {1, 4, 7} }; // Function call System.out.println(findRotation(mat, T)); }} |
Python3
# Python program for the above approach# Function to check whether another# matrix can be created by rotating# mat one or more times by 90 degreesdef findRotation(mat, T): # If the dimensions of both the # arrays don't match if len(T) != len(mat) or len(T[0]) != len(mat[0]): # Return false return "No" # Map to store all rows, columns # and their reversed versions m = {} # Iterate in the range [0, M-1] for i in range(len(mat)): # Increment the frequency of the # i'th row by 1 m[tuple(mat[i])] = m.get(tuple(mat[i]), 0) + 1 # Reverse the i'th row mat[i].reverse() # Increment the frequency of the # i'th row by 1 m[tuple(mat[i])] = m.get(tuple(mat[i]), 0) + 1 # Iterate in the range [0, N-1] for i in range(len(mat[0])): # Stores the i'th column r = [] # Iterate in the range [0, M-1] for j in range(len(mat)): r.append(mat[j][i]) # Increment the frequency of the # i'th column by 1 m[tuple(r)] = m.get(tuple(r), 0) + 1 # Reverse the i'th column r.reverse() # Increment the frequency of the # i'th column by 1 m[tuple(r)] = m.get(tuple(r), 0) + 1 # Iterate in the range [0, M-1] for i in range(len(T)): # If frequency of the i'th row # is more in T[][] than in the # mat[][]. if m.get(tuple(T[i]), 0) <= 0: return "No" # Decrement the frequency of the # i'th row by 1 m[tuple(T[i])] -= 1 # Iterate in the range [0, N-1] for i in range(len(T[0])): # Stores the ith column r = [] # Iterate in the range [0, M-1] for j in range(len(T)): r.append(T[j][i]) # If frequency of the i'th column # is more in T[][] than in mat[][]. if m.get(tuple(r), 0) <= 0: return "No" # Decrement the frequency of the i'th # column by 1 m[tuple(r)] -= 1 # Return "Yes" return "Yes"# Driver codeif __name__ == "__main__": # Input mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] T = [[3, 6, 9], [2, 5, 8], [1, 4, 7]] # Function call print(findRotation(mat, T)) |
C#
using System;using System.Collections.Generic;using System.Linq;class GFG{ // Function to check whether another matrix can be created by rotating mat one or more times by 90 degrees static string FindRotation(List<List<int>> mat, List<List<int>> T) { // If the dimensions of both the arrays don't match if (T.Count != mat.Count || T[0].Count != mat[0].Count) { // Return false return "No"; } // Dictionary to store all rows, columns, and their reversed versions Dictionary<string, int> m = new Dictionary<string, int>(); // Iterate through rows foreach (var row in mat) { // Increment the frequency of the row string rowString = string.Join(", ", row); if (m.ContainsKey(rowString)) { m[rowString]++; } else { m[rowString] = 1; } // Reverse the row row.Reverse(); // Increment the frequency of the reversed row rowString = string.Join(", ", row); if (m.ContainsKey(rowString)) { m[rowString]++; } else { m[rowString] = 1; } } // Iterate through columns for (int i = 0; i < mat[0].Count; i++) { // Stores the i'th column var column = new List<int>(); foreach (var row in mat) { column.Add(row[i]); } // Increment the frequency of the column string columnString = string.Join(", ", column); if (m.ContainsKey(columnString)) { m[columnString]++; } else { m[columnString] = 1; } // Reverse the column column.Reverse(); // Increment the frequency of the reversed column columnString = string.Join(", ", column); if (m.ContainsKey(columnString)) { m[columnString]++; } else { m[columnString] = 1; } } // Iterate through T to check if each row and column exists in mat foreach (var row in T) { string rowString = string.Join(", ", row); if (!m.ContainsKey(rowString) || m[rowString] <= 0) { return "No"; } m[rowString]--; } for (int i = 0; i < T[0].Count; i++) { var column = new List<int>(); foreach (var row in T) { column.Add(row[i]); } string columnString = string.Join(", ", column); if (!m.ContainsKey(columnString) || m[columnString] <= 0) { return "No"; } m[columnString]--; } // Return "Yes" return "Yes"; } static void Main() { // Input List<List<int>> mat = new List<List<int>> { new List<int> {1, 2, 3}, new List<int> {4, 5, 6}, new List<int> {7, 8, 9} }; List<List<int>> T = new List<List<int>> { new List<int> {3, 6, 9}, new List<int> {2, 5, 8}, new List<int> {1, 4, 7} }; // Function call Console.WriteLine(FindRotation(mat, T)); }}// code is contributed by shinjanpatra |
Javascript
<script>// JavaScript program for the above approach// Function to check whether another// matrix can be created by rotating// mat one or more times by 90 degreesfunction findRotation(mat, T){ // If the dimensions of both the // arrays don't match if (T.length != mat.length || T[0].length != mat[0].length) { // Return false return "No"; } // Map to store all rows, columns // and their reversed versions let m = new Map(); // Iterate in the range [0, M-1] for (let i = 0; i < mat.length; i++) { // Increment the frequency of the // i'th row by 1 if(m.has(mat[i])){ m.set(mat[i], m.get(mat[i]) + 1) }else{ m.set(mat[i], 1) } // Reverse the i'th row mat[i].reverse(); // Increment the frequency of the // i'th row by 1 if(m.has(mat[i])){ m.set(mat[i], m.get(mat[i]) + 1) }else{ m.set(mat[i], 1) } } // Iterate in the range [0, N-1] for (let i = 0; i < mat[0].length; i++) { // Stores the i'th column let r = []; // Iterate in the range [0, M-1] for (let j = 0; j < mat.length; j++) { r.push(mat[j][i]); } // Increment the frequency of the // i'th column by 1 if(m.has(r)){ m.set(r, m.get(r) + 1) }else{ m.set(r, 1) } // Reverse the i'th column r.reverse(); // Increment the frequency of the // i'th column by 1 if(m.has(r)){ m.set(r, m.get(r) + 1) }else{ m.set(r, 1) } } // Iterate in the range [0, M-1] for (let i = 0; i < T.length; i++) { // If frequency of the i'th row // is more in T[][] than in the // mat[][]. if (m.get(T[i]) <= 0) { return "No"; } // Decrement the frequency of the // i'th row by 1 m.set(T[i], m.get(T[i]) - 1); } // Iterate in the range [0, N-1] for (let i = 0; i < T[0].length; i++) { // Stores the ith column let r = []; // Iterate in the range [0, M-1] for (let j = 0; j < T.length; j++) { r.push(T[j][i]); } // If frequency of the i'th column // is more in T[][] than in mat[][]. if (m.get(r) <= 0) { return "No"; } // Decrement the frequency of the i'th // column by 1 m.set(r, m.get(r) - 1); } // Return "Yes" return "Yes";}// Driver code // Input let mat = [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]; let T = [ [ 3, 6, 9 ], [ 2, 5, 8 ], [ 1, 4, 7 ] ]; // Function call document.write(findRotation(mat, T)); </script> |
Output
Yes
Time Complexity: O(N*M)
Auxiliary Space: (N*M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
