#1886

Easy

LeetCode Problem Workspace

Determine Whether Matrix Can Be Obtained By Rotation

Determine if a binary matrix can be transformed into another by rotating it 90 degrees multiple times.

Problem Statement

You are given two n x n binary matrices: mat and target. The task is to determine if it is possible to transform mat into target by rotating mat in 90-degree increments.

Return true if any rotation of mat matches target, otherwise return false. The rotation should be considered clockwise, and you can rotate the matrix up to three times to cover all possible 90-degree rotations.

Examples

Example 1

Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]]

Output: true

We can rotate mat 90 degrees clockwise to make mat equal target.

Example 2

Input: mat = [[0,1],[1,1]], target = [[1,0],[0,1]]

Output: false

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

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.

Solution Approach

Brute Force with 4 Rotations

One approach is to manually rotate the matrix 0, 90, 180, and 270 degrees. For each rotation, check if the resulting matrix is equal to the target. This brute-force solution is simple but not the most efficient.

Matrix Rotation Function

Create a function to rotate the matrix by 90 degrees clockwise. Apply this function successively to check all four possible rotations. This method reduces redundancy in rotation logic but still evaluates all rotations.

Optimized Check

Instead of rotating multiple times, consider checking if the matrix and target matrices have the same content, since any rotations should have the same set of values. If the content matches, a rotation is possible.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The brute-force solution requires checking 4 rotations of the matrix, each with a time complexity of O(n^2), where n is the size of the matrix. Hence, the overall time complexity is O(4n^2), which simplifies to O(n^2). Space complexity is O(n^2) due to the storage required for the matrix and its rotated versions.

What Interviewers Usually Probe

Candidate demonstrates understanding of matrix manipulation.
Candidate implements multiple rotations efficiently.
Candidate chooses the simplest solution if time constraints allow.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle all four rotations (0, 90, 180, 270 degrees).
Incorrectly checking matrix equality after rotation, leading to false negatives.
Overcomplicating the solution with unnecessary optimizations.

Follow-up variants

What if the matrix is not binary, but contains other integer values?
How would the solution change if the matrix was non-square (rectangular)?
Can you optimize further if the matrix size is fixed and small?

FAQ

How do I rotate a matrix in this problem?

To rotate the matrix, transpose it and then reverse each row. Repeat this up to three times to check all possible 90-degree rotations.

What is the time complexity of the brute force approach?

The brute force approach checks four rotations, each with a time complexity of O(n^2), so the overall complexity is O(n^2).

How do I compare matrices after rotation?

You can compare matrices element by element. If all elements match, the matrices are equal, otherwise they are not.

What if the matrix size increases?

For larger matrices, the brute force solution can be slower. Optimizing the comparison or reducing redundant rotations could help.

Why is the matrix rotation approach relevant to this problem?

The matrix rotation approach is directly related because the task asks you to determine if one matrix can be obtained from another through 90-degree rotations.

terminal

Solution

Solution 1: In-Place Comparison

We observe the rotation pattern of the matrix and find that for an element $\text{mat}[i][j]$, after rotating 90 degrees it appears at position $\text{mat}[j][n-1-i]$, after rotating 180 degrees it appears at position $\text{mat}[n-1-i][n-1-j]$, and after rotating 270 degrees it appears at position $\text{mat}[n-1-j][i]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        n = len(mat)
        ok = 0b1111
        for i in range(n):
            for j in range(n):
                if mat[i][j] != target[i][j]:
                    ok &= ~0b0001
                if mat[j][n - 1 - i] != target[i][j]:
                    ok &= ~0b0010
                if mat[n - 1 - i][n - 1 - j] != target[i][j]:
                    ok &= ~0b0100
                if mat[n - 1 - j][i] != target[i][j]:
                    ok &= ~0b1000
                if ok == 0:
                    return False
        return ok != 0

Continue Practicing

#1878 get biggest three rhombus sums in a grid #1895 largest magic square #1901 find a peak element ii