Determine Whether Matrix Can Be Obtained By Rotation

Difficulty: Easy | Acceptance: 68.30% | Paid: No Topics: Array, Matrix

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.

• Examples
• Constraints
• Simulation
• Index Mapping

Examples

Example 1:

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

Example 2:

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:

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 three times to make mat equal target.

Constraints

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

Simulation

Intuition Since the matrix is square (n x n), rotating it 4 times brings it back to the original state. We can simulate the rotation process up to 3 times and check for equality after each rotation.

Steps

• Check if mat is already equal to target.
• Rotate mat 90 degrees clockwise.
• Repeat the check and rotation process 3 more times.
• If any check passes, return true; otherwise, return false.

class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        for _ in range(4):
            if mat == target:
                return True
            mat = [list(row) for row in zip(*mat[::-1])]
        return False

Complexity

• Time: O(n²)
• Space: O(n²)
• Notes: We use extra space to store the rotated matrix.

Index Mapping

Intuition Instead of physically rotating the matrix, we can determine the corresponding indices in the original matrix for each cell in the target matrix for all 4 possible rotations (0°, 90°, 180°, 270°). If all cells match for any of these rotation states, the answer is true.

Steps

• Initialize four boolean flags representing the four possible rotation states (0°, 90°, 180°, 270°) to true.
• Iterate through every cell (i, j) in the matrix.
• For each cell, check if mat[i][j] matches target[i][j] (0°), mat[n-1-j][i] (90°), mat[n-1-i][n-1-j] (180°), or mat[j][n-1-i] (270°).
• If a mismatch is found for a specific rotation, set its corresponding flag to false.
• If any flag remains true after checking all cells, return true.

class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        n = len(mat)
        c0 = c90 = c180 = c270 = True
        for i in range(n):
            for j in range(n):
                if mat[i][j] != target[i][j]: c0 = False
                if mat[n-1-j][i] != target[i][j]: c90 = False
                if mat[n-1-i][n-1-j] != target[i][j]: c180 = False
                if mat[j][n-1-i] != target[i][j]: c270 = False
        return c0 or c90 or c180 or c270

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: This approach is optimal in terms of space complexity as it only uses a few extra variables.