Given a matrix mat[][] with N rows and M columns. The task is to find the minimum number of changes required in the matrix such that every path from top left to bottom right is a palindromic path. In a path only right and bottom movements are allowed from one cell to another cell.
Examples:
Input: M = 2, N = 2, mat[M][N] = {{0, 0}, {0, 1}}
Output: 1
Explanation:
Change matrix[0][0] from 0 to 1. The two paths from (0, 0) to (1, 1) become palindromic.Input: M = 3, N = 7, mat[M][N] = {{1, 2, 3, 4, 5, 6, 7}, {2, 2, 3, 3, 4, 3, 2}, {1, 2, 3, 2, 5, 6, 4}}
Output: 10
Naive Approach: For the Naive Approach please refer to this article.
Time Complexity: O(N^3)
Auxiliary Space: O(N)
Efficient Approach:
The following observations have to be made:
- A unique diagonal exists for every value (i+j) where i is the row index and j is the column index.
- The task reduces to selecting two diagonals, which are at the same distance from cell (0, 0) and cell (M – 1, N – 1) respectively and making all their elements equal to a single number, which is repeated most number of times in both the chosen diagonals.
- If the number of elements between cell (0, 0) and (M – 1, N – 1) are odd, then a common diagonal equidistant from both the cells exists. Elements of that diagonal need not be modified as they do not affect the palindromic arrangement of a path.
- If the numbers of cells between (0, 0) and (M – 1, N – 1) are even, no such common diagonal exists.
Follow the below steps to solve the problem:
- Create a 2D array frequency_diagonal that stores the frequency of all numbers in each chosen diagonal.
- Each diagonal can be uniquely represented as the sum of (i, j).
- Initialize a count variable that stores the count of the total number of cells where the values have to be replaced.
- Iterate over the mat[][] and increment the frequency of current element in the diagonal ((i + j) value) where it belongs to.
- Initialize a variable number_of_elements to 1, which stores the number of elements in each of the currently chosen pair of diagonals.
- Initialize start = 0 and end = M + N – 2 and repeat the steps below until start < end:
- Find the frequency of the number which appears maximum times in the two selected diagonals that are equidistant from (0, 0) and (M-1, N-1).
- Let the frequency in the above step be X. Add the value (total number of elements in the two diagonals – X) to count the minimum number of changes.
- Increment start by 1 and decrement end by 1 and if the number of elements in the current diagonal is less than the maximum possible elements in any diagonal of the matrix, then increment number_of_elements by 1.
- Print the value of total count after the above steps.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the minimum// number of replacementsint MinReplacements( int M, int N, int mat[][30]){ // 2D array to store frequency // of all the numbers in // each diagonal int frequency_diagonal[100][10005]; // Initialise all the elements // of 2D array with 0 memset(frequency_diagonal, 0, sizeof(frequency_diagonal)); // Initialise answer as 0 int answer = 0; // Iterate over the matrix for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // Update the frequency of // number mat[i][j] // for the diagonal // identified by (i+j) frequency_diagonal[i + j] [(mat[i][j])]++; } } // Initialize start as 0 // which indicates the // first diagonal int start = 0; // Initialize end as // M + N - 2 which indicates // the last diagonal int end = M + N - 2; // Number of elements in // the current diagonal int no_of_elemnts = 1; // Maximum possible number // of elements in a diagonal // can be minimum of (number of // rows and number of columns) int max_elements = min(M, N); while (start < end) { // The frequency of number // which occurs for the // maximum number of times // in the two selected // diagonals int X = INT_MIN; for (int i = 0; i <= 10000; i++) { X = max( X, frequency_diagonal[start][i] + frequency_diagonal[end][i]); } answer = answer + (2 * (no_of_elemnts)) - X; // Increment start start++; // Decrement end end--; // Increment current number // of elements until it reaches // the maximum possible value if (no_of_elemnts < max_elements) no_of_elemnts++; } // return the final answer return answer;}// Driver Codeint main(){ // Number of rows int M = 3; // Number of columns int N = 7; int mat[30][30] = { { 1, 2, 3, 4, 5, 6, 7 }, { 2, 2, 3, 3, 4, 3, 2 }, { 1, 2, 3, 2, 5, 6, 4 } }; cout << MinReplacements(M, N, mat) << endl;} |
Java
// Java program of the above approachclass GFG{// Function to calculate the minimum// number of replacementsstatic int MinReplacements(int M, int N, int mat[][]){ // 2D array to store frequency // of all the numbers in // each diagonal int [][]frequency_diagonal = new int[100][10005]; // Initialise answer as 0 int answer = 0; // Iterate over the matrix for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { // Update the frequency of // number mat[i][j] // for the diagonal // identified by (i+j) frequency_diagonal[i + j][(mat[i][j])]++; } } // Initialize start as 0 // which indicates the // first diagonal int start = 0; // Initialize end as // M + N - 2 which indicates // the last diagonal int end = M + N - 2; // Number of elements in // the current diagonal int no_of_elemnts = 1; // Maximum possible number // of elements in a diagonal // can be minimum of (number of // rows and number of columns) int max_elements = Math.min(M, N); while (start < end) { // The frequency of number // which occurs for the // maximum number of times // in the two selected // diagonals int X = Integer.MIN_VALUE; for(int i = 0; i <= 10000; i++) { X = Math.max(X, frequency_diagonal[start][i] + frequency_diagonal[end][i]); } answer = answer + (2 * (no_of_elemnts)) - X; // Increment start start++; // Decrement end end--; // Increment current number // of elements until it reaches // the maximum possible value if (no_of_elemnts < max_elements) no_of_elemnts++; } // return the final answer return answer;}// Driver Codepublic static void main(String[] args){ // Number of rows int M = 3; // Number of columns int N = 7; int mat[][] = { { 1, 2, 3, 4, 5, 6, 7 }, { 2, 2, 3, 3, 4, 3, 2 }, { 1, 2, 3, 2, 5, 6, 4 } }; System.out.print(MinReplacements(M, N, mat) + "\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program of the above approachimport sys# Function to calculate the minimum# number of replacementsdef MinReplacements(M, N, mat): # 2D array to store frequency # of all the numbers in # each diagonal frequency_diagonal = [[0 for x in range(10005)] for y in range (100)]; # Initialise answer as 0 answer = 0 # Iterate over the matrix for i in range(M): for j in range(N): # Update the frequency of # number mat[i][j] # for the diagonal # identified by (i+j) frequency_diagonal[i + j][(mat[i][j])] += 1 # Initialize start as 0 # which indicates the # first diagonal start = 0 # Initialize end as # M + N - 2 which indicates # the last diagonal end = M + N - 2 # Number of elements in # the current diagonal no_of_elemnts = 1 # Maximum possible number # of elements in a diagonal # can be minimum of (number of # rows and number of columns) max_elements = min(M, N) while (start < end): # The frequency of number # which occurs for the # maximum number of times # in the two selected # diagonals X = -sys.maxsize - 1 for i in range(10001): X = max(X, frequency_diagonal[start][i] + frequency_diagonal[end][i]) answer = answer + (2 * (no_of_elemnts)) - X # Increment start start += 1 # Decrement end end -= 1 # Increment current number # of elements until it reaches # the maximum possible value if (no_of_elemnts < max_elements): no_of_elemnts += 1 # Return the final answer return answer# Driver Code# Number of rowsM = 3# Number of columnsN = 7mat = [ [ 1, 2, 3, 4, 5, 6, 7 ], [ 2, 2, 3, 3, 4, 3, 2 ], [ 1, 2, 3, 2, 5, 6, 4 ] ]print(MinReplacements(M, N, mat))# This code is contributed by chitranayal |
C#
// C# program of the above approachusing System;class GFG{// Function to calculate the minimum// number of replacementsstatic int MinReplacements(int M, int N, int [,]mat){ // 2D array to store frequency // of all the numbers in // each diagonal int [,]frequency_diagonal = new int[100, 10005]; // Initialise answer as 0 int answer = 0; // Iterate over the matrix for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { // Update the frequency of // number mat[i,j] // for the diagonal // identified by (i+j) frequency_diagonal[i + j, mat[i, j]]++; } } // Initialize start as 0 // which indicates the // first diagonal int start = 0; // Initialize end as // M + N - 2 which indicates // the last diagonal int end = M + N - 2; // Number of elements in // the current diagonal int no_of_elemnts = 1; // Maximum possible number // of elements in a diagonal // can be minimum of (number of // rows and number of columns) int max_elements = Math.Min(M, N); while (start < end) { // The frequency of number // which occurs for the // maximum number of times // in the two selected // diagonals int X = int.MinValue; for(int i = 0; i <= 10000; i++) { X = Math.Max(X, frequency_diagonal[start, i] + frequency_diagonal[end, i]); } answer = answer + (2 * (no_of_elemnts)) - X; // Increment start start++; // Decrement end end--; // Increment current number // of elements until it reaches // the maximum possible value if (no_of_elemnts < max_elements) no_of_elemnts++; } // Return the readonly answer return answer;}// Driver Codepublic static void Main(String[] args){ // Number of rows int M = 3; // Number of columns int N = 7; int [,]mat = { { 1, 2, 3, 4, 5, 6, 7 }, { 2, 2, 3, 3, 4, 3, 2 }, { 1, 2, 3, 2, 5, 6, 4 } }; Console.Write(MinReplacements(M, N, mat) + "\n");}}// This code is contributed by amal kumar choubey |
Javascript
<script>// Javascript program of the above approach// Function to calculate the minimum// number of replacementsfunction MinReplacements(M,N,mat){ // 2D array to store frequency // of all the numbers in // each diagonal let frequency_diagonal = new Array(100); for(let i=0;i<100;i++) { frequency_diagonal[i]=new Array(10005); for(let j=0;j<10005;j++) { frequency_diagonal[i][j]=0; } } // Initialise answer as 0 let answer = 0; // Iterate over the matrix for(let i = 0; i < M; i++) { for(let j = 0; j < N; j++) { // Update the frequency of // number mat[i][j] // for the diagonal // identified by (i+j) frequency_diagonal[i + j][(mat[i][j])]++; } } // Initialize start as 0 // which indicates the // first diagonal let start = 0; // Initialize end as // M + N - 2 which indicates // the last diagonal let end = M + N - 2; // Number of elements in // the current diagonal let no_of_elemnts = 1; // Maximum possible number // of elements in a diagonal // can be minimum of (number of // rows and number of columns) let max_elements = Math.min(M, N); while (start < end) { // The frequency of number // which occurs for the // maximum number of times // in the two selected // diagonals let X = Number.MIN_VALUE; for(let i = 0; i <= 10000; i++) { X = Math.max(X, frequency_diagonal[start][i] + frequency_diagonal[end][i]); } answer = answer + (2 * (no_of_elemnts)) - X; // Increment start start++; // Decrement end end--; // Increment current number // of elements until it reaches // the maximum possible value if (no_of_elemnts < max_elements) no_of_elemnts++; } // return the final answer return answer;}// Driver Code// Number of rows let M = 3; // Number of columns let N = 7; let mat = [[ 1, 2, 3, 4, 5, 6, 7 ], [ 2, 2, 3, 3, 4, 3, 2 ], [ 1, 2, 3, 2, 5, 6, 4 ]]; document.write(MinReplacements(M, N, mat) + "<br>");// This code is contributed by avanitrachhadiya2155</script> |
Output:
10
Time Complexity: O(M * N), The program iterates over the matrix using two nested loops, so the time complexity of the program is O(M*N), where M is the number of rows and N is the number of columns of the matrix. In addition, it has a loop that iterates over the frequency array, which has a fixed size of 10000, so it can be considered as a constant time operation. Therefore, the overall time complexity of the program is O(M*N).
Auxiliary Space: O(M * N), The space complexity of the program is O(M*N), as the program uses a 2D array of size 100×10005 to store the frequency of each element in each diagonal. Therefore, the space complexity of the program is also linear in terms of the size of the input.
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!
