Determine Whether matrix can be obtained via rotation

XXX. Matrix Rotation Check

Matrix

Math

Problem Statement:

Given two n x n binary matrices, determine if one matrix can become equal to another matrix after some number of 90-degree rotations.

• Matrix can be rotated 0°, 90°, 180°, or 270°
• All rotations are clockwise
• Matrices must match exactly after rotation

Implementation:

public boolean findRotation(int[][] a, int[][] b) {
    int n = a.length;
    // Counters for each possible rotation
    int c90 = 0, c180 = 0, c270 = 0, c0 = 0;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            // Check 90° rotation: [i,j] -> [n-j-1,i]
            if(b[i][j] == a[n-j-1][i])
                c90++;
                
            // Check 180° rotation: [i,j] -> [n-i-1,n-j-1]
            if(b[i][j] == a[n-i-1][n-j-1])
                c180++;
                
            // Check 270° rotation: [i,j] -> [j,n-i-1]
            if(b[i][j] == a[j][n-i-1])
                c270++;
                
            // Check no rotation: [i,j] -> [i,j]
            if(b[i][j] == a[i][j])
                c0++;
        }
    }
    
    // Return true if any rotation matches all elements
    return c90 == n*n || c180 == n*n || 
           c270 == n*n || c0 == n*n;
}

Complexity:

Time Complexity: O(n²), single pass through matrix
Space Complexity: O(1), only uses counters

Key Points:

• **Rotation Mappings**:
  • 90°: [i,j] → [n-j-1,i]
  • 180°: [i,j] → [n-i-1,n-j-1]
  • 270°: [i,j] → [j,n-i-1]
  • 0°: [i,j] → [i,j]
• **Counting Strategy**:
  • Check all rotations simultaneously
  • Count matching elements for each rotation
  • Need all elements to match for valid rotation

Example:

For 2x2 matrices:

Matrix A:    Matrix B:
1 0         0 1
0 1         1 0
        

• 90° rotation of A matches B:
  • [0,0] → [1,0]: 1→0 ✓
  • [0,1] → [0,0]: 0→0 ✓
  • [1,0] → [1,1]: 0→1 ✓
  • [1,1] → [0,1]: 1→1 ✓
• c90 = 4 = n*n, so return true

Implementation Notes:

• **Efficiency**:
  • Checks all rotations in single pass
  • No need for actual rotation
  • Early exit not possible due to counting
• **Edge Cases**:
  • 1x1 matrices always match
  • Identical matrices match without rotation
  • Handle 0 elements correctly