Given a matrix startMatrix and another matrix finalMatrix, the task is to check if startMatrix can be converted to finalMatrix by column exchanges and a row exchanges.
Examples:
Input: start[][] = {{1, 2, 3, 4},
{5, 6, 7, 8}
{9, 10, 11, 12},
{13, 14, 15, 16}}
final[][] = {{1, 4, 3, 2},
{5, 8, 7, 6},
{13, 16, 15, 14},
{9, 12, 11, 10}}
Output: Yes
Explanation: Exchanging 2nd and 4th column followed by 4th and 3rd row gives the desired matrixInput: start[][] = {{1, 2, 3, 4},
{5, 6, 7, 8}
{9, 10, 11, 12},
{13, 14, 15, 16}}
final[][] = {{1, 4, 3, 2},
{5, 6, 7, 8},
{13, 16, 15, 14},
{9, 12, 11, 10}}
Output: No
Approach:
In order to solve this problem we just need to check whether the elements in all rows and columns in startMatrix are preserved in the finalMatrix matrix irrespective of their order. Any violation of this condition will ensure that the finalMatrix matrix can’t be obtained. Traverse a loop through every row and check if all elements of that row in startMatrix is present in a single row in finalMatrix. Then transpose both startMatrix and finalMatrix and repeat the same verification.
Below code is the implementation of the above approach:
C++
// CPP program to check if a// given matrix can be converted// to another given matrix by row// and column exchanges#include <bits/stdc++.h>using namespace std;// Function to get transpose of a matrixvector<vector<int>> getTranspose(vector<vector<int>> matrix){ int n = matrix.size(); vector<vector<int>> transpose(n, vector<int>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { transpose[j][i] = matrix[i][j]; } } return transpose;}// Function to check for row preservationbool rowEquality(vector<vector<int>> s, vector<vector<int>> f){ vector<set<int>> sets, setf; unordered_map<int, int> map; // Creating sets from the initial matrix for (int i = 0; i < s.size(); i++) { // Create set for corresponding row set<int> sett; // Add first element to the set sett.insert(s[i][0]); sets.push_back(sett); // Store the row number in map map[s[i][0]] = i; // Add remaining elements to the set for (int j = 1; j < s.size(); j++) { sett.insert(s[i][j]); } } // Create sets for final matrix // and check with the initial matrix int rowIndex = -1; for (int i = 0; i < f.size(); i++) { rowIndex = -1; set<int> sett; for (int j = 0; j < f.size(); j++) { sett.insert(f[i][j]); if (map.find(f[i][j]) != map.end()) { rowIndex = map[f[i][j]]; } } setf.push_back(sett); if (setf[i] != sets[rowIndex]) return true; } return false;}// Driver codeint main() { vector<vector<int>> startMatrix = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16} }; vector<vector<int>> finalMatrix = { {3, 4, 1, 2}, {15, 16, 13, 14}, {7, 8, 5, 6}, {11, 12, 9, 10} }; vector<vector<int>> startTranspose = getTranspose(startMatrix); vector<vector<int>> finalTranspose = getTranspose(finalMatrix); if (rowEquality(startMatrix, finalMatrix) && rowEquality(startTranspose, finalTranspose)) cout << "Yes" << endl; else cout << "No" << endl;}// This code is contributed by sanjeev2552 |
Java
// Java program to check if a // given matrix can be converted // to another given matrix by row// and column exchangesimport java.util.*;public class Solution{ // Function to get transpose of a matrix static int[][] getTranspose(int[][] matrix){ int n = matrix.length; int[][] transpose = new int[n][n]; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ transpose[j][i] = matrix[i][j]; } } return transpose; } // Function to check for row preservation static boolean rowEquality(int[][] s, int[][] f){ ArrayList<Set<Integer>> sets = new ArrayList<>(); ArrayList<Set<Integer>> setf = new ArrayList<>(); HashMap<Integer,Integer> map = new HashMap<>(); // Creating sets from the initial matrix for(int i=0; i<s.length; i++){ // Create set for corresponding row Set<Integer> set = new HashSet<Integer>(); // Add first element to the set set.add(s[i][0]); sets.add(set); // Store the row number in map map.put(s[i][0], i); // Add remaining elements to the set for(int j=1; j<s.length; j++){ set.add(s[i][j]); } } // Create sets for final matrix // and check with the initial matrix int rowIndex = -1; for(int i=0; i<f.length; i++){ rowIndex = -1; Set<Integer> set = new HashSet<Integer>(); for(int j=0; j<f.length; j++){ set.add(f[i][j]); if(map.containsKey(f[i][j])){ rowIndex = map.get(f[i][j]); } } setf.add(set); if(rowIndex != -1 && !setf.get(i).equals( sets.get(rowIndex))) return false; } return true; } // Driver code public static void main(String []args){ int[][] startMatrix = {{ 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 }}; int[][] finalMatrix = {{ 3, 4, 1, 2 }, { 15, 16, 13, 14 }, { 7, 8, 5, 6 }, { 11, 12, 9, 10 }}; int[][] startTranspose = getTranspose(startMatrix); int[][] finalTranspose = getTranspose(finalMatrix); if(rowEquality(startMatrix,finalMatrix) && rowEquality(startTranspose,finalTranspose)) System.out.println("Yes"); else System.out.println("No"); }} |
Python3
# Python3 program to check if a # given matrix can be converted # to another given matrix by row# and column exchanges# Function to get transpose of a matrixdef getTranspose(matrix): n = len(matrix) transpose = [[0 for i in range(n)] for j in range(n)] for i in range(n): for j in range(n): transpose[j][i] = matrix[i][j] return transpose# Function to check for row preservationdef rowEquality(s, f): sets = [] setf = [] mp = {i : 0 for i in range(100)} # Creating sets from the initial matrix for i in range(len(s)): # Create set for corresponding row st = set() # Add first element to the set st.add(s[i][0]) sets.append(st) # Store the row number in mp mp[s[i][0]] = i # Add remaining elements to the set for j in range(1, len(s)): st.add(s[i][j]) # Create sets for final matrix # and check with the initial matrix rowIndex = -1 for i in range(len(f)): rowIndex = -1; st1 = set() for j in range(len(f)): st1.add(f[i][j]) if(f[i][j] in mp): rowIndex = mp[f[i][j]] setf.append(st1) if(rowIndex != -1 and setf[i] != sets[rowIndex]): return True return False #Driver codeif __name__ == '__main__': startMatrix = [[ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ]] finalMatrix = [[ 3, 4, 1, 2], [ 15, 16, 13, 14 ], [ 7, 8, 5, 6 ], [ 11, 12, 9, 10 ]] startTranspose = getTranspose(startMatrix) finalTranspose = getTranspose(finalMatrix) if(rowEquality(startMatrix, finalMatrix) and rowEquality(startTranspose, finalTranspose)): print("Yes") else: print("No")# This code is contributed by Samarth |
C#
// C# program to check if a // given matrix can be converted // to another given matrix by row// and column exchangesusing System;using System.Collections.Generic;class GFG{// Function to get transpose of a matrixstatic int[,] getTranspose(int[,] matrix){ int n = matrix.GetLength(0); int[,] transpose = new int[n, n]; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { transpose[j, i] = matrix[i, j]; } } return transpose;}// Function to check for row preservationstatic bool rowEquality(int[,] s, int[,] f){ List<HashSet<int>> sets = new List<HashSet<int>>(); List<HashSet<int>> setf = new List<HashSet<int>>(); Dictionary<int, int> map = new Dictionary<int, int>(); // Creating sets from the initial matrix for(int i = 0; i < s.GetLength(0); i++) { // Create set for corresponding row HashSet<int> set = new HashSet<int>(); // Add first element to the set set.Add(s[i, 0]); sets.Add(set); // Store the row number in map map.Add(s[i, 0], i); // Add remaining elements to the set for(int j = 1; j < s.GetLength(1); j++) { set.Add(s[i, j]); } } // Create sets for readonly matrix // and check with the initial matrix int rowIndex = -1; for(int i = 0; i < f.GetLength(0); i++) { rowIndex = -1; HashSet<int> set = new HashSet<int>(); for(int j = 0; j < f.GetLength(1); j++) { set.Add(f[i, j]); if (map.ContainsKey(f[i, j])) { rowIndex = map[f[i, j]]; } } setf.Add(set); if (rowIndex != -1 && !setf[i].Equals(sets[rowIndex])) return true; } return false; }// Driver codepublic static void Main(String []args){ int[,] startMatrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; int[,] finalMatrix = { { 3, 4, 1, 2 }, { 15, 16, 13, 14 }, { 7, 8, 5, 6 }, { 11, 12, 9, 10 } }; int[,] startTranspose = getTranspose(startMatrix); int[,] finalTranspose = getTranspose(finalMatrix); if (rowEquality(startMatrix,finalMatrix) && rowEquality(startTranspose,finalTranspose)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by Princi Singh |
Javascript
<script>// JavaScript program to check if a// given matrix can be converted// to another given matrix by row// && column exchanges// Function to get transpose of a matrixfunction getTranspose(matrix){ let n = matrix.length let transpose = new Array(n); for(let i=0;i<n;i++){ transpose[i] = new Array(n).fill(0); } for(let i=0;i<n;i++){ for(let j=0;j<n;j++){ transpose[j][i] = matrix[i][j] } } return transpose}// Function to check for row preservationfunction rowEquality(s, f){ let sets = [] let setf = [] let mp = new Map(); for(let i=0;i<100;i++){ mp.set(i,0); } // Creating sets from the initial matrix for(let i=0;i<s.length;i++){ // Create set for corresponding row let st = new Set() // Add first element to the set st.add(s[i][0]) sets.push(st) // Store the row number in mp mp.set(s[i][0],i) // Add remaining elements to the set for(let j=1;j<s.length;j++) st.add(s[i][j]) } // Create sets for final matrix // && check with the initial matrix let rowIndex = -1 for(let i=0;i<f.length;i++){ rowIndex = -1; let st1 = new Set() for(let j=0;j<f.length;j++){ st1.add(f[i][j]) if(mp.has(f[i][j])) rowIndex = mp.get(f[i][j]) } setf.push(st1) if(rowIndex != -1 && setf[i] !=sets[rowIndex]) return true } return false} //Driver codelet startMatrix = [[ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ]]let finalMatrix = [[ 3, 4, 1, 2], [ 15, 16, 13, 14 ], [ 7, 8, 5, 6 ], [ 11, 12, 9, 10 ]] let startTranspose = getTranspose(startMatrix)let finalTranspose = getTranspose(finalMatrix)if(rowEquality(startMatrix, finalMatrix) && rowEquality(startTranspose, finalTranspose)) document.write("Yes")else document.write("No")// This code is contributed by Shinjanpatra</script> |
Output:
Yes
Time Complexity: O(N2)
Auxiliary Space: O(N2)
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!
