Given a matrix with N rows and M columns, the task is to find the minimum replacements required to make all rows and columns of a given matrix palindromic.
Examples:
Input: a[][] = {{1, 2, 3}, {4, 5, 3}, {1, 2, 1}}
Output: 2
Explanation: To make the given matrix palindromic, replace a[0][2] by 1 and replace a[1][2] by 4.Input: a[][] = {{1, 2, 4}, {4, 5, 6}}
Output: 3
Explanation: To make a given matrix palindromic, replace a[0][0] by 4, a[1][2] by 4 and a[[0][1] by 5.
Approach: The idea is to select the set of four cells of the matrix as discussed below and proceed accordingly.
- To make each row and each column of the matrix palindromic, traverse over the given matrix, and for every cell (i, j) (i = [0, N/2], j = [0, M/2]), select a set of the following four cells:
- Make the value of all these four cells equal to the most frequent value among the four of them. Count the replacements thus required.
- After completing the above steps, print the count of replacements performed.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count minimum // changes to make the matrix // palindromic int minchanges(vector<vector<int> > mat) { // Rows in the matrix int N = mat.size(); // Columns in the matrix int M = mat[0].size(); int i, j, ans = 0, x; map<int, int> mp; // Traverse the given matrix for (i = 0; i < N / 2; i++) { for (j = 0; j < M / 2; j++) { // Store the frequency of // the four cells mp[(mat[i][M - 1 - j])]++; mp[(mat[i][j])]++; mp[(mat[N - 1 - i][M - 1 - j])]++; mp[(mat[N - 1 - i][j])]++; x = 0; // Iterate over the map for (auto it = mp.begin(); it != mp.end(); it++) { x = max(x, it->second); } // Min changes to do to make all ans = ans + 4 - x; // Four elements equal mp.clear(); } } // Make the middle row palindromic if (N % 2 == 1) { for (i = 0; i < M / 2; i++) { if (mat[N / 2][i] != mat[N / 2][M - 1 - i]) ans++; } } if (M % 2 == 1) { for (i = 0; i < N / 2; i++) { // Make the middle column // palindromic if (mat[i][M / 2] != mat[N - 1 - i][M / 2]) ans++; } } // Print minimum changes cout << ans; } // Driver Code int main() { // Given matrix vector<vector<int> > mat{ { 1, 2, 3 }, { 4, 5, 3 }, { 1, 2, 1 } }; // Function Call minchanges(mat); } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to count minimum // changes to make the matrix // palindromic static void minchanges(int [][]mat) { // Rows in the matrix int N = mat.length; // Columns in the matrix int M = mat[0].length; int i, j, ans = 0, x; HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // Traverse the given matrix for (i = 0; i < N / 2; i++) { for (j = 0; j < M / 2; j++) { // Store the frequency of // the four cells if(mp.containsKey(mat[i][M - 1 - j])) { mp.put(mat[i][M - 1 - j], mp.get(mat[i][M - 1 - j]) + 1); } else { mp.put(mat[i][M - 1 - j], 1); } if(mp.containsKey(mat[i][j])) { mp.put(mat[i][j], mp.get(mat[i][j]) + 1); } else { mp.put(mat[i][j], 1); } if(mp.containsKey(mat[N - 1 - i][M - 1 - j])) { mp.put(mat[N - 1 - i][M - 1 - j], mp.get(mat[N - 1 - i][M - 1 - j]) + 1); } else { mp.put(mat[N - 1 - i][M - 1 - j], 1); } if(mp.containsKey(mat[N - 1 - i][j])) { mp.put(mat[N - 1 - i][j], mp.get(mat[N - 1 - i][j])+1); } else { mp.put(mat[N - 1 - i][j], 1); } x = 0; // Iterate over the map for (Map.Entry<Integer,Integer> it : mp.entrySet()) { x = Math.max(x, it.getValue()); } // Min changes to do to make all ans = ans + 4 - x; // Four elements equal mp.clear(); } } // Make the middle row palindromic if (N % 2 == 1) { for (i = 0; i < M / 2; i++) { if (mat[N / 2][i] != mat[N / 2][M - 1 - i]) ans++; } } if (M % 2 == 1) { for (i = 0; i < N / 2; i++) { // Make the middle column // palindromic if (mat[i][M / 2] != mat[N - 1 - i][M / 2]) ans++; } } // Print minimum changes System.out.print(ans); } // Driver Code public static void main(String[] args) { // Given matrix int [][]mat = { { 1, 2, 3 }, { 4, 5, 3 }, { 1, 2, 1 } }; // Function Call minchanges(mat); } } // This code is contributed by shikhasingrajput |
Python
# Python program for the above approach # Function to count minimum # changes to make the matrix # palindromic def minchanges(mat) : # Rows in the matrix N = len(mat) # Columns in the matrix M = len(mat[0]) ans = 0 mp = {} # Traverse the given matrix for i in range(N//2): for j in range(M//2): # Store the frequency of # the four cells mp[(mat[i][M - 1 - j])] = mp.get(mat[i][M - 1 - j], 0) + 1 mp[(mat[i][j])] = mp.get(mat[i][j], 0) + 1 mp[(mat[N - 1 - i][M - 1 - j])] = mp.get(mat[N - 1 - i][M - 1 - j], 0) + 1 mp[(mat[N - 1 - i][j])] = mp.get(mat[N - 1 - i][j], 0) + 1 x = 0 # Iterate over the map for it in mp: x = max(x, mp[it]) # Min changes to do to make all ans = ans + 4 - x # Four elements equal mp.clear() # Make the middle row palindromic if (N % 2 == 1) : for i in range(M // 2): if (mat[N // 2][i] != mat[N // 2][M - 1 - i]) : ans += 1 if (M % 2 == 1) : for i in range(N // 2): # Make the middle column # palindromic if (mat[i][M // 2] != mat[N - 1 - i][M // 2]): ans += 1 # Print minimum changes print(ans) # Driver Code # Given matrix mat = [[ 1, 2, 3 ], [ 4, 5, 3 ], [1, 2, 1 ]] # Function Call minchanges(mat) # This code is contributed by susmitakundugoaldanga |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to count minimum // changes to make the matrix // palindromic static void minchanges(int [,]mat) { // Rows in the matrix int N = mat.GetLength(0); // Columns in the matrix int M = mat.GetLength(1); int i, j, ans = 0, x; Dictionary<int,int> mp = new Dictionary<int,int>(); // Traverse the given matrix for (i = 0; i < N / 2; i++) { for (j = 0; j < M / 2; j++) { // Store the frequency of // the four cells if(mp.ContainsKey(mat[i,M - 1 - j])) { mp[(mat[i,M - 1 - j])]= mp[(mat[i,M - 1 - j])] + 1; } else { mp.Add(mat[i,M - 1 - j], 1); } if(mp.ContainsKey(mat[i,j])) { mp[(mat[i,j])] = mp[(mat[i,j])] + 1; } else { mp.Add(mat[i,j], 1); } if(mp.ContainsKey(mat[N - 1 - i,M - 1 - j])) { mp[(mat[N - 1 - i,M - 1 - j])]= mp[(mat[N - 1 - i,M - 1 - j])] + 1; } else { mp.Add(mat[N - 1 - i,M - 1 - j], 1); } if(mp.ContainsKey(mat[N - 1 - i,j])) { mp[(mat[N - 1 - i,j])] = mp[(mat[N - 1 - i,j)]]+1; } else { mp.Add(mat[N - 1 - i,j], 1); } x = 0; // Iterate over the map foreach (KeyValuePair<int,int> it in mp) { x = Math.Max(x, it.Value); } // Min changes to do to make all ans = ans + 4 - x; // Four elements equal mp.Clear(); } } // Make the middle row palindromic if (N % 2 == 1) { for (i = 0; i < M / 2; i++) { if (mat[N / 2,i] != mat[N / 2,M - 1 - i]) ans++; } } if (M % 2 == 1) { for (i = 0; i < N / 2; i++) { // Make the middle column // palindromic if (mat[i,M / 2] != mat[N - 1 - i,M / 2]) ans++; } } // Print minimum changes Console.Write(ans); } // Driver Code public static void Main(String[] args) { // Given matrix int [,]mat = { { 1, 2, 3 }, { 4, 5, 3 }, { 1, 2, 1 } }; // Function Call minchanges(mat); } } // This code contributed by shikhasingrajput |
Javascript
<script> // JavaScript program for the above approach // Function to count minimum // changes to make the matrix // palindromic function minchanges(mat) { // Rows in the matrix var N = mat.length; // Columns in the matrix var M = mat[0].length; var i, j, ans = 0, x; var mp = {}; // Traverse the given matrix for (i = 0; i < parseInt(N / 2); i++) { for (j = 0; j < parseInt(M / 2); j++) { // Store the frequency of // the four cells if (mp.hasOwnProperty(mat[i][M - 1 - j])) { mp[(mat[i][M - 1 - j])] = mp[(mat[i][M - 1 - j])] + 1; } else { mp[(mat[i][M - 1 - j])] = 1; } if (mp.hasOwnProperty(mat[i][j])) { mp[(mat[(i, j)])] = mp[(mat[i][j])] + 1; } else { mp[(mat[i][j])] = 1; } if (mp.hasOwnProperty(mat[N - 1 - i][M - 1 - j])) { mp[(mat[N - 1 - i][M - 1 - j])] = mp[(mat[N - 1 - i][M - 1 - j])] + 1; } else { mp[(mat[N - 1 - i][M - 1 - j])] = 1; } if (mp.hasOwnProperty(mat[N - 1 - i][j])) { mp[(mat[N - 1 - i][j])] = mp[(mat[N - 1 - i][j])] + 1; } else { mp[(mat[(N - 1 - i, j)])] = 1; } x = 0; // Iterate over the map for (const [key, value] of Object.entries(mp)) { x = Math.max(x, value); } // Min changes to do to make all ans = ans + 4 - x; // Four elements equal mp = {}; } } // Make the middle row palindromic if (N % 2 === 1) { for (i = 0; i < parseInt(M / 2); i++) { if (mat[parseInt(N / 2)][i] != mat[parseInt(N / 2)][M - 1 - i]) ans++; } } if (M % 2 === 1) { for (i = 0; i < parseInt(N / 2); i++) { // Make the middle column // palindromic if (mat[i][parseInt(M / 2)] != mat[N - 1 - i][parseInt(M / 2)]) ans++; } } // Print minimum changes document.write(ans); } // Driver Code // Given matrix var mat = [ [1, 2, 3], [4, 5, 3], [1, 2, 1], ]; // Function Call minchanges(mat); </script> |
Output:
2
Time Complexity: O(N × M)
Auxiliary Space: O(1)
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!