# Determine Whether Matrix Can Be Obtained By Rotation
**Difficulty:** EASY
[External](https://leetcode.com/problems/determine-whether-matrix-can-be-obtained-by-rotation)
Canonical: https://scaleengineer.com/dsa/problems/determine-whether-matrix-can-be-obtained-by-rotation
**Data structures:** Array, Matrix
---
## Problem
Given two `n x n` binary matrices `mat` and `target`, return `true` _if it is possible to make_ `mat` _equal to_ `target` _by **rotating**_ `mat` _in **90-degree increments**, or_ `false` _otherwise._

**Example 1:**

![](https://assets.glich.co/dsa/determine-whether-matrix-can-be-obtained-by-rotation/image0.png) 

**Input:** mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
**Output:** true
**Explanation:** We can rotate mat 90 degrees clockwise to make mat equal target.

**Example 2:**

![](https://assets.glich.co/dsa/determine-whether-matrix-can-be-obtained-by-rotation/image1.png) 

**Input:** mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
**Output:** false
**Explanation:** It is impossible to make mat equal to target by rotating mat.

**Example 3:**

![](https://assets.glich.co/dsa/determine-whether-matrix-can-be-obtained-by-rotation/image2.png) 

**Input:** mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
**Output:** true
**Explanation:** We can rotate mat 90 degrees clockwise two times to make mat equal target.

**Constraints:**

* `n == mat.length == target.length`
* `n == mat[i].length == target[i].length`
* `1 <= n <= 10`
* `mat[i][j]` and `target[i][j]` are either `0` or `1`.

# Approaches
## Simulate Rotations with Auxiliary Matrix
This approach directly simulates the process of rotating the matrix. We generate each of the four possible rotations (0, 90, 180, and 270 degrees) one by one and compare each result with the `target` matrix. For each rotation, a new auxiliary matrix is created to store the result.
**Time:** O(N^2). We perform a constant number of rotations (up to 3) and comparisons (up to 4). Each of these operations takes O(N^2) time to iterate through all the elements of the matrix. · **Space:** O(N^2), where N is the dimension of the matrix. This is because we create a new N x N matrix to store the result of each rotation.
**Pros:** The logic is straightforward and easy to understand as it directly models the physical rotation.; It does not modify the original input matrix.
**Cons:** Requires extra space proportional to the size of the matrix, which can be inefficient for large matrices.
### Explanation
The fundamental idea is to check every possible orientation of the `mat` matrix against the `target` matrix. A matrix can be rotated 90 degrees clockwise three times before returning to its original state on the fourth rotation. This gives us four states to check.

We can implement this by:
1.  First, checking if the original `mat` is equal to `target`.
2.  If not, we create a new matrix, `rotated90`, by applying the 90-degree rotation formula: `rotated[j][n-1-i] = original[i][j]`. We then compare `rotated90` with `target`.
3.  If there's still no match, we rotate `rotated90` to get `rotated180` and compare that with `target`.
4.  Finally, we rotate `rotated180` to get `rotated270` and perform the last comparison.

If any of these comparisons return true, the function returns `true`. If all four checks fail, it returns `false`.

```java
class Solution {
    public boolean findRotation(int[][] mat, int[][] target) {
        // Check 0 degree rotation
        if (areEqual(mat, target)) return true;
        
        // Check 90, 180, 270 degree rotations
        int[][] rotatedMat = mat;
        for (int i = 0; i < 3; i++) {
            rotatedMat = rotate(rotatedMat);
            if (areEqual(rotatedMat, target)) {
                return true;
            }
        }
        
        return false;
    }

    private int[][] rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] newMatrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                newMatrix[j][n - 1 - i] = matrix[i][j];
            }
        }
        return newMatrix;
    }

    private boolean areEqual(int[][] mat1, int[][] mat2) {
        int n = mat1.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (mat1[i][j] != mat2[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Create a helper function `areEqual(mat1, mat2)` to compare two matrices element by element. It takes `O(N^2)` time.
- Create a helper function `rotate(matrix)` that takes a matrix and returns a new `N x N` matrix, which is the 90-degree clockwise rotation of the input. This also takes `O(N^2)` time and space.
- In the main function, start with the original matrix `mat`.
- In a loop that runs 4 times (for 0, 90, 180, and 270-degree rotations):
  1. Call `areEqual` to compare the current state of `mat` with `target`. If they are equal, return `true`.
  2. If not equal, call `rotate` to get the next rotated version of the matrix.
- If the loop completes without finding a match, return `false`.

## Simulate Rotations In-Place
This approach improves upon the first one by optimizing space. Instead of creating a new matrix for each rotation, we perform the rotation 'in-place', meaning we modify the `mat` matrix directly. This eliminates the need for `O(N^2)` auxiliary space.
**Time:** O(N^2). The structure is similar to the first approach. We perform a constant number of comparisons and in-place rotations, each taking O(N^2) time. · **Space:** O(1). The rotation is performed in-place, so no extra space proportional to the input size is required.
**Pros:** Highly space-efficient, using only constant extra space.; The time complexity remains optimal at O(N^2).
**Cons:** This approach modifies the input matrix `mat`, which might be undesirable in certain scenarios where the original matrix needs to be preserved.
### Explanation
The overall logic is the same as the previous approach: check, rotate, and repeat. The key difference is how the rotation is performed. An in-place 90-degree clockwise rotation is a two-step process:

1.  **Transpose the matrix:** For each element `mat[i][j]`, swap it with `mat[j][i]`. We only need to iterate through the upper or lower triangle of the matrix to avoid swapping elements back to their original place.
2.  **Reverse each row:** For each row `i`, swap the element at column `j` with the element at column `n-1-j`, iterating `j` from `0` to `n/2 - 1`.

We can loop four times. In each iteration, we first check for equality with `target`, and if it fails, we rotate `mat` in-place for the next check.

```java
class Solution {
    public boolean findRotation(int[][] mat, int[][] target) {
        for (int i = 0; i < 4; i++) {
            if (areEqual(mat, target)) {
                return true;
            }
            rotateInPlace(mat);
        }
        return false;
    }

    private void rotateInPlace(int[][] matrix) {
        int n = matrix.length;
        // Transpose the matrix
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // Reverse each row
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }

    private boolean areEqual(int[][] mat1, int[][] mat2) {
        int n = mat1.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (mat1[i][j] != mat2[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Create a helper function `areEqual(mat1, mat2)` to compare two matrices, which takes `O(N^2)` time.
- Create a helper function `rotateInPlace(matrix)` that rotates the given matrix 90 degrees clockwise without using extra space. This can be done by first transposing the matrix and then reversing each row.
- In the main function, loop four times.
- In each iteration, first check if `mat` is equal to `target` using `areEqual`. If it is, return `true`.
- After the check, call `rotateInPlace(mat)` to prepare for the next iteration's check.
- If the loop finishes, it means no rotation matched, so return `false`.

## Check All Rotations in a Single Pass via Index Mapping
This is the most efficient approach. Instead of creating new rotated matrices or modifying the input, we can check all four rotation possibilities in a single pass through the matrices. We use mathematical formulas to find the corresponding coordinates in the `target` matrix for each element in the `mat` matrix for every possible rotation.
**Time:** O(N^2). We iterate through each element of the matrix once. Inside the loop, we perform a constant number of comparisons. This is the optimal time complexity as we must inspect every element at least once. · **Space:** O(1). We only use a few boolean variables to track the validity of each rotation, which is constant space.
**Pros:** Most efficient in terms of both time and space.; Requires only a single pass through the matrices.; Uses constant extra space.; Does not modify the input matrices.
**Cons:** The index manipulation logic can be slightly more complex to reason about and implement correctly compared to direct simulation.
### Explanation
The core of this method lies in understanding the coordinate transformation for each rotation. An element at `mat[i][j]` moves to a new position depending on the rotation angle. We can check if `target` is a rotated version of `mat` by reversing this logic. For example, for `target` to be a 90-degree clockwise rotation of `mat`, the element `target[j][n-1-i]` must be equal to `mat[i][j]` for all `i` and `j`.

The coordinate mappings are:
- **0 degrees:** `mat[i][j]` corresponds to `target[i][j]`
- **90 degrees:** `mat[i][j]` corresponds to `target[j][n-1-i]`
- **180 degrees:** `mat[i][j]` corresponds to `target[n-1-i][n-1-j]`
- **270 degrees:** `mat[i][j]` corresponds to `target[n-1-j][i]`

We can maintain four boolean flags, one for each rotation, initially all `true`. We then iterate through the matrix once. In each step, we check all four conditions. If a condition is violated, we set the corresponding flag to `false`. After checking all elements, if at least one flag remains `true`, it means a valid rotation exists.

```java
class Solution {
    public boolean findRotation(int[][] mat, int[][] target) {
        int n = mat.length;
        boolean c0 = true, c90 = true, c180 = true, c270 = true;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 0-degree rotation check
                if (mat[i][j] != target[i][j]) c0 = false;
                // 90-degree rotation check
                if (mat[i][j] != target[j][n - 1 - i]) c90 = false;
                // 180-degree rotation check
                if (mat[i][j] != target[n - 1 - i][n - 1 - j]) c180 = false;
                // 270-degree rotation check
                if (mat[i][j] != target[n - 1 - j][i]) c270 = false;
            }
        }

        return c0 || c90 || c180 || c270;
    }
}
```
### Algorithm
- Initialize four boolean flags, `check0`, `check90`, `check180`, `check270`, to `true`.
- Iterate through the matrix with indices `i` from `0` to `N-1` and `j` from `0` to `N-1`.
- In each iteration, check the element `mat[i][j]` against the corresponding element in `target` for all four possible rotations using index mapping:
  - **0°:** `target[i][j]`
  - **90°:** `target[j][N-1-i]`
  - **180°:** `target[N-1-i][N-1-j]`
  - **270°:** `target[N-1-j][i]`
- If a comparison for a specific rotation fails, set its corresponding boolean flag to `false`.
- After the loops complete, return `true` if any of the four flags is still `true`, otherwise return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean findRotation(int[][] mat, int[][] target) {
    int times = 4;
    while (times-- > 0) {
      if (equals(mat, target)) {
        return true;
      }
      rotate(mat);
    }
    return false;
  }
private
  void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n / 2; ++i) {
      for (int j = i; j < n - 1 - i; ++j) {
        int t = matrix[i][j];
        matrix[i][j] = matrix[n - j - 1][i];
        matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
        matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
        matrix[j][n - i - 1] = t;
      }
    }
  }
private
  boolean equals(int[][] nums1, int[][] nums2) {
    int n = nums1.length;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (nums1[i][j] != nums2[i][j]) {
          return false;
        }
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool findRotation(vector<vector<int>> &mat, vector<vector<int>> &target) {
    int n = mat.size();
    for (int k = 0; k < 4; ++k) {
      vector<vector<int>> g(n, vector<int>(n));
      for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
          g[i][j] = mat[j][n - i - 1];
      if (g == target)
        return true;
      mat = g;
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool: def rotate(matrix): n = len(matrix) for i in range(n // 2): for j in range(i, n - 1 - i): t = matrix[i][j] matrix[i][j] = matrix[n - j - 1][i] matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1] matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1] matrix[j][n - i - 1] = t for _ in range(4): if mat == target: return True rotate(mat) return False

```