Code Implementation

class Solution:
    def findRotation(self, mat, target):
        def rotate(mat):
            n = len(mat)
            return [[mat[n - j - 1][i] for j in range(n)] for i in range(n)]
        
        for _ in range(4):
            if mat == target:
                return True
            mat = rotate(mat)
        return False
      

class Solution {
public:
    bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
        int n = mat.size();
        for (int r = 0; r < 4; ++r) {
            if (mat == target) return true;
            // Rotate 90 degrees clockwise
            vector<vector<int>> rotated(n, vector<int>(n));
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    rotated[j][n - i - 1] = mat[i][j];
            mat = rotated;
        }
        return false;
    }
};
      

class Solution {
    public boolean findRotation(int[][] mat, int[][] target) {
        int n = mat.length;
        for (int r = 0; r < 4; ++r) {
            if (isSame(mat, target)) return true;
            mat = rotate(mat);
        }
        return false;
    }
    
    private boolean isSame(int[][] a, int[][] b) {
        for (int i = 0; i < a.length; ++i)
            for (int j = 0; j < a[0].length; ++j)
                if (a[i][j] != b[i][j]) return false;
        return true;
    }
    
    private int[][] rotate(int[][] mat) {
        int n = mat.length;
        int[][] res = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                res[j][n - i - 1] = mat[i][j];
        return res;
    }
}
      

var findRotation = function(mat, target) {
    const n = mat.length;
    function rotate(mat) {
        let res = Array.from({length: n}, () => Array(n));
        for (let i = 0; i < n; ++i)
            for (let j = 0; j < n; ++j)
                res[j][n - i - 1] = mat[i][j];
        return res;
    }
    for (let r = 0; r < 4; ++r) {
        let same = true;
        for (let i = 0; i < n; ++i)
            for (let j = 0; j < n; ++j)
                if (mat[i][j] !== target[i][j]) same = false;
        if (same) return true;
        mat = rotate(mat);
    }
    return false;
};
      

Problem Description

You are given two square matrices of size n x n: mat and target. Your task is to determine if you can obtain target by rotating mat by 0, 90, 180, or 270 degrees clockwise (i.e., in increments of 90 degrees).

• You may rotate mat any number of times (including zero).
• Each rotation must be 90 degrees clockwise.
• You cannot rearrange or swap individual elements except by rotation.
• Return true if mat can be rotated to match target; otherwise, return false.

Thought Process

The problem asks if two matrices can be made equal by rotating one of them. The most direct approach is to simulate each possible rotation (0, 90, 180, 270 degrees) and check if the resulting matrix matches the target.

At first glance, a brute-force way would be to generate all possible rotations and compare each with target. Since there are only four possible states (because rotating four times brings the matrix back to its original form), this is feasible.

We can optimize by stopping as soon as we find a match, and by writing a helper function to perform a 90-degree rotation efficiently. This avoids unnecessary computation and keeps the code clean.

Solution Approach

We will approach the problem step-by-step:

1. Rotation Function: Write a function to rotate a matrix 90 degrees clockwise. For a square matrix, this means that element mat[i][j] moves to mat[j][n - i - 1] in the new matrix.
2. Check All Rotations: Starting from the original matrix, perform up to three rotations (for a total of four configurations including the original). After each rotation, compare the current matrix to target.
3. Comparison: Use a simple nested loop or direct matrix comparison (if supported in your language) to check if the matrices are equal.
4. Return Result: If any rotation matches, return true. If none match after four tries, return false.

This approach is efficient because the number of possible rotations is fixed and small, and each comparison is straightforward.

Example Walkthrough

Suppose mat is:

    1 2
    3 4
  

And target is:

    3 1
    4 2
  

1. Original (0°):
   mat:
   1 2
   3 4
   Not equal to target.
2. Rotate 90°:
   Rotated matrix:
   3 1
   4 2
   Now, mat matches target.
3. Since a match is found after one rotation, we return true.

Time and Space Complexity

• Brute-force: For each rotation (4 in total), we compare all n^2 elements. Each rotation also takes O(n^2) time to create a new matrix. Therefore, the overall time complexity is O(4 * n^2) = O(n^2).
• Space Complexity: Each rotation can create a new matrix, which uses O(n^2) space. However, this is acceptable since n is typically small (as per Leetcode constraints).
• Optimized Approach: Since we always check after each rotation and can return early, in the best case (if mat matches target immediately), we only do one comparison.

Summary

To determine whether a matrix can be obtained by rotating another matrix, we simulate up to four 90-degree rotations, checking for equality with the target after each. This direct approach is efficient and leverages the fact that there are only four possible configurations. The solution is both simple and robust, making it well-suited for this problem.