The Palindrome Pattern

JavaView on GFG

Time: O(n*m)

Space: O(1)

Problem Overview

Find row or column in matrix where mirroring makes entire matrix palindromic.

Intuition

Find row or column in matrix where mirroring makes entire matrix palindromic. Check each row/column.

Algorithm

1For each row: check if all columns are palindromic with this row as mirror axis. Similarly for columns.

Common Pitfalls

• O(n^3) brute force. For each axis candidate: verify palindrome property across all rows and columns.

The Palindrome Pattern.java

Java

// Approach: Check each row and column for palindrome property. Report row/column indices with this property.
// Time: O(n*m) Space: O(1)
class Solution {
    public String pattern(int[][] arr) {
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(arr[i][j]);
            }

            String s = sb.toString();
            String reversed = new StringBuilder(s).reverse().toString();

            if (s.equals(reversed))
                return i + " R";
        }

        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(arr[j][i]);
            }

            String s = sb.toString();
            String reversed = new StringBuilder(s).reverse().toString();

            if (s.equals(reversed))
                return i + " C";
        }

        return "-1";
    }
}

Was this solution helpful?