Given a matrix arr[][] of size N * N, the task is to find the number of palindromic rows.
Examples:
Input: arr[][] = {{1, 3, 1},
{2, 2, 3},
{2, 1, 2}}
Output: 2
Explanation: First and third row forms a palindrome i.e 1 3 1 and 2 1 2.
Therefore, count of palindromic rows is 2.Input: arr[][] = {{2, 2, 3, 2},
{1, 3, 3, 1},
{4, 2, 2, 4},
{5, 6, 6, 5}}
Output: 3
Approach: The task can be solved using a two-pointer approach. Follow the steps mentioned below:
- Iterate over each row of the matrix.
- For each row:
- Use two pointers to point the starting of the row and the end of the row.
- If values of both the pointer are same increment the starting pointer and decrement the end pointer.
- Keep on doing this until both the pointers point to the same element or they have different values.
- If they have different values the row is not a palindrome. Stop the iteration and return false. Else continue for the next row.
- After all the rows are traversed and everyone is palindrome return true.
Below is the implementation of the approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; const int MAX = 100; // Function to count the number of // palindromic rows int countPalindrome( vector<vector< int > >& arr, int N) { int count = 0; for ( int i = 0; i < N; i++) { int j = 0, k = N - 1; bool t = true ; while (j < k) { if (arr[i][j] != arr[i][k]) { t = false ; break ; } j++; k--; } if (t) count++; } return count; } // Driver Code int main() { int N = 3; vector<vector< int > > arr = { { 1, 3, 1 }, { 2, 2, 3 }, { 2, 1, 2 } }; cout << countPalindrome(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class Solution { // Function to count the number of // palindromic rows static int countPalindrome( int arr[][], int N) { int count = 0 ; for ( int i = 0 ; i < N; i++) { int j = 0 , k = N - 1 ; boolean t = true ; while (j < k) { if (arr[i][j] != arr[i][k]) { t = false ; break ; } j++; k--; } if (t) count++; } return count; } // Driver code public static void main(String[] args) { int N = 3 ; int arr[][] = { { 1 , 3 , 1 }, { 2 , 2 , 3 }, { 2 , 1 , 2 } }; System.out.println( countPalindrome(arr, N)); } } |
Python3
# Python program for the above approach MAX = 100 ; # Function to count the number of # palindromic rows def countPalindrome(arr, N): count = 0 ; for i in range (N): j = 0 k = N - 1 t = True while (j < k): if (arr[i][j] ! = arr[i][k]): t = False break ; j + = 1 k - = 1 if (t): count + = 1 return count; # Driver Code N = 3 ; arr = [[ 1 , 3 , 1 ], [ 2 , 2 , 3 ], [ 2 , 1 , 2 ]]; print (countPalindrome(arr, N)); # This code is contributed by gfgking |
C#
// C# program for the above approach using System; public class GFG{ // Function to count the number of // palindromic rows static int countPalindrome( int [,] arr, int N) { int count = 0; for ( int i = 0; i < N; i++) { int j = 0, k = N - 1; bool t = true ; while (j < k) { if (arr[i, j] != arr[i, k]) { t = false ; break ; } j++; k--; } if (t) count++; } return count; } // Driver code static public void Main (){ int N = 3; int [,] arr = new int [3, 3] { { 1, 3, 1 }, { 2, 2, 3 }, { 2, 1, 2 } }; Console.WriteLine( countPalindrome(arr, N)); } } // This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript program for the above approach const MAX = 100; // Function to count the number of // palindromic rows const countPalindrome = (arr, N) => { let count = 0; for (let i = 0; i < N; i++) { let j = 0, k = N - 1; let t = true ; while (j < k) { if (arr[i][j] != arr[i][k]) { t = false ; break ; } j++; k--; } if (t) count++; } return count; } // Driver Code let N = 3; let arr = [[1, 3, 1], [2, 2, 3], [2, 1, 2]]; document.write(countPalindrome(arr, N)); // This code is contributed by rakeshsahni </script> |
2
Time Complexity: O(N*N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!