Given a matrix mat[][] of dimensions N*M, the task is to check if all the diagonals of the matrix(from top-right to bottom-left) are palindromic or not. If found to be true, then print Yes. Otherwise, print No.
Examples:
Input: mat[][] = [[1, 0, 0, 0], [0, 1, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]]
Output: Yes
Explanation:
All the diagonals of the matrix mat[][] is given by:
- {1}
- {0, 0}
- {0, 1, 0}
- {0, 1, 1, 0}
- {1, 0, 1}
- {1, 1}
- {0}
As all the above diagonals are palindromic. Therefore, print Yes.
Input: mat[][] = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 1]]
Output: No
Approach: The given problem can be solved by performing the diagonal traversal of the matrix and for every diagonal traversal check if the elements are palindromic or not. If there exists any such diagonal which is not palindromic, then print Yes. Otherwise, print No.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define N 5// Function to check if the matrix is// palindrome or notstring isbinaryMatrixPalindrome( int mat[N][N]){ // Traverse the matrix and check if // top right and bottom left elements // have same value for (int i = 0; i < N - 1; i++) { for (int j = N - 1; j > i; j--) { // If top right element is not // equal to the bottom left // element return false if (mat[i][j] != mat[j][i]) { return "Np"; } } } return "Yes";}// Driver Codeint main(){ int mat[N][N] = { { 1, 0, 0, 1, 1 }, { 0, 1, 0, 1, 0 }, { 0, 0, 1, 1, 1 }, { 1, 1, 1, 0, 1 }, { 1, 0, 1, 1, 0 } }; cout << isbinaryMatrixPalindrome(mat); return 0;} |
Java
// Java program for the above approachpublic class GFG { final static int N = 5; // Function to check if the matrix is // palindrome or not static String isbinaryMatrixPalindrome(int mat[][]) { // Traverse the matrix and check if // top right and bottom left elements // have same value for (int i = 0; i < N - 1; i++) { for (int j = N - 1; j > i; j--) { // If top right element is not // equal to the bottom left // element return false if (mat[i][j] != mat[j][i]) { return "Np"; } } } return "Yes"; } // Driver Code public static void main (String[] args) { int mat[][] = { { 1, 0, 0, 1, 1 }, { 0, 1, 0, 1, 0 }, { 0, 0, 1, 1, 1 }, { 1, 1, 1, 0, 1 }, { 1, 0, 1, 1, 0 } }; System.out.println(isbinaryMatrixPalindrome(mat)); }}// This code is contributed by AnkThon |
Python3
# python program for the above approachN = 5# Function to check if the matrix is# palindrome or notdef isbinaryMatrixPalindrome(mat): # Traverse the matrix and check if # top right and bottom left elements # have same value for i in range(0, N - 1): for j in range(N - 1, i, -1): # If top right element is not # equal to the bottom left # element return false if (mat[i][j] != mat[j][i]): return "No" return "Yes"# Driver Codeif __name__ == "__main__": mat = [[1, 0, 0, 1, 1], [0, 1, 0, 1, 0], [0, 0, 1, 1, 1], [1, 1, 1, 0, 1], [1, 0, 1, 1, 0]] print(isbinaryMatrixPalindrome(mat)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;public class GFG { static int N = 5; // Function to check if the matrix is // palindrome or not static string isbinaryMatrixPalindrome(int [,]mat) { // Traverse the matrix and check if // top right and bottom left elements // have same value for (int i = 0; i < N - 1; i++) { for (int j = N - 1; j > i; j--) { // If top right element is not // equal to the bottom left // element return false if (mat[i, j] != mat[j, i]) { return "Np"; } } } return "Yes"; } // Driver Code public static void Main (string[] args) { int [,]mat = { { 1, 0, 0, 1, 1 }, { 0, 1, 0, 1, 0 }, { 0, 0, 1, 1, 1 }, { 1, 1, 1, 0, 1 }, { 1, 0, 1, 1, 0 } }; Console.WriteLine(isbinaryMatrixPalindrome(mat)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approachlet N = 5;// Function to check if the matrix is// palindrome or notfunction isbinaryMatrixPalindrome(mat){ // Traverse the matrix and check if // top right and bottom left elements // have same value for (let i = 0; i < N - 1; i++) { for (let j = N - 1; j > i; j--) { // If top right element is not // equal to the bottom left // element return false if (mat[i][j] != mat[j][i]) { return "Np"; } } } return "Yes";}// Driver Codelet mat = [ [1, 0, 0, 1, 1], [0, 1, 0, 1, 0], [0, 0, 1, 1, 1], [1, 1, 1, 0, 1], [1, 0, 1, 1, 0],];document.write(isbinaryMatrixPalindrome(mat));// This code is contributed by saurabh_jaiswal.</script> |
Output:
Yes
Time Complexity: O(N2)
Auxiliary Space: O(1)
Another Approach:
- Traverse each diagonal of the matrix from top-right to bottom-left.
- For each diagonal, create a temporary string and append each element in the diagonal to it.
- Check if the temporary string is a palindrome. If not, return “No”.
- If all diagonals are palindromic, return “Yes”.
Below is the implementation of the above approach:
C++
#include <iostream>#include <string>using namespace std;#define N 4#define M 4// Function to check if a string is a palindromebool isPalindrome(string s) { int n = s.length(); for (int i = 0; i < n/2; i++) { if (s[i] != s[n-i-1]) { return false; } } return true;}// Function to check if all diagonals of a matrix are palindromicstring isDiagonalPalindrome(int mat[N][M]) { // Traverse diagonals starting from top-right corner for (int i = 0; i < N; i++) { string s = ""; int x = i, y = M-1; while (x < N && y >= 0) { s += to_string(mat[x][y]); x++; y--; } if (!isPalindrome(s)) { return "No"; } } // Traverse diagonals starting from top-left corner for (int j = M-1; j >= 0; j--) { string s = ""; int x = 0, y = j; while (x < N && y >= 0) { s += to_string(mat[x][y]); x++; y--; } if (!isPalindrome(s)) { return "No"; } } return "Yes";}// Driver codeint main() { int mat[N][M] = {{1, 0, 0, 0}, {0, 1, 1, 1}, {0, 1, 0, 1}, {0, 1, 1, 0}}; cout << isDiagonalPalindrome(mat) << endl; return 0;} |
Java
import java.util.*;class Main { static final int N = 4; static final int M = 4; // Function to check if a string is a palindrome static boolean isPalindrome(String s) { int n = s.length(); for (int i = 0; i < n/2; i++) { if (s.charAt(i) != s.charAt(n-i-1)) { return false; } } return true; } // Function to check if all diagonals of a matrix are palindromic static String isDiagonalPalindrome(int[][] mat) { // Traverse diagonals starting from top-right corner for (int i = 0; i < N; i++) { StringBuilder s = new StringBuilder(); int x = i, y = M-1; while (x < N && y >= 0) { s.append(mat[x][y]); x++; y--; } if (!isPalindrome(s.toString())) { return "No"; } } // Traverse diagonals starting from top-left corner for (int j = M-1; j >= 0; j--) { StringBuilder s = new StringBuilder(); int x = 0, y = j; while (x < N && y >= 0) { s.append(mat[x][y]); x++; y--; } if (!isPalindrome(s.toString())) { return "No"; } } return "Yes"; } // Driver code public static void main(String[] args) { int[][] mat = {{1, 0, 0, 0}, {0, 1, 1, 1}, {0, 1, 0, 1}, {0, 1, 1, 0}}; System.out.println(isDiagonalPalindrome(mat)); }} |
Python3
# Python3 code to check if all diagonals of a matrix are palindromic# Function to check if a string is a palindromedef isPalindrome(s): n = len(s) for i in range(n // 2): if s[i] != s[n - i - 1]: return False return True# Function to check if all diagonals of a matrix are palindromicdef isDiagonalPalindrome(mat): # Traverse diagonals starting from top-right corner for i in range(N): s = "" x, y = i, M - 1 while x < N and y >= 0: s += str(mat[x][y]) x += 1 y -= 1 if not isPalindrome(s): return "No" # Traverse diagonals starting from top-left corner for j in range(M - 1, -1, -1): s = "" x, y = 0, j while x < N and y >= 0: s += str(mat[x][y]) x += 1 y -= 1 if not isPalindrome(s): return "No" return "Yes"# Driver codeif __name__ == '__main__': N, M = 4, 4 mat = [[1, 0, 0, 0], [0, 1, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]] print(isDiagonalPalindrome(mat)) |
C#
using System;public class MainClass{ // Function to check if a string is a palindrome public static bool IsPalindrome(string s) { int n = s.Length; for (int i = 0; i < n / 2; i++) { if (s[i] != s[n - i - 1]) { return false; } } return true; } // Function to check if all diagonals of a matrix are // palindromic public static string IsDiagonalPalindrome(int[, ] mat) { int N = mat.GetLength(0); int M = mat.GetLength(1); // Traverse diagonals starting from top-right corner for (int i = 0; i < N; i++) { string s = ""; int x = i, y = M - 1; while (x < N && y >= 0) { s += mat[x, y].ToString(); x++; y--; } if (!IsPalindrome(s)) { return "No"; } } // Traverse diagonals starting from top-left corner for (int j = M - 1; j >= 0; j--) { string s = ""; int x = 0, y = j; while (x < N && y >= 0) { s += mat[x, y].ToString(); x++; y--; } if (!IsPalindrome(s)) { return "No"; } } return "Yes"; } public static void Main() { int[, ] mat = { { 1, 0, 0, 0 }, { 0, 1, 1, 1 }, { 0, 1, 0, 1 }, { 0, 1, 1, 0 } }; Console.WriteLine(IsDiagonalPalindrome(mat)); }} |
Javascript
// Function to check if a string is a palindromefunction isPalindrome(s) { let n = s.length; for (let i = 0; i < n / 2; i++) { if (s[i] != s[n - i - 1]) { return false; } } return true;}// Function to check if all diagonals of a matrix are palindromicfunction isDiagonalPalindrome(mat) { // Traverse diagonals starting from top-right corner for (let i = 0; i < N; i++) { let s = ""; let x = i, y = M - 1; while (x < N && y >= 0) { s += mat[x][y].toString(); x++; y--; } if (!isPalindrome(s)) { return "No"; } } // Traverse diagonals starting from top-left corner for (let j = M - 1; j >= 0; j--) { let s = ""; let x = 0, y = j; while (x < N && y >= 0) { s += mat[x][y].toString(); x++; y--; } if (!isPalindrome(s)) { return "No"; } } return "Yes";}// Driver codeconst N = 4, M = 4;let mat = [ [1, 0, 0, 0], [0, 1, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]];console.log(isDiagonalPalindrome(mat)); |
Output
Yes
Time complexity: O(NM^2)
Auxiliary Space: O(NM)
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!
