Problem Statement in English

You’re given two $n \times n$ binary matrices mat and target. You want to know if it is possible to make mat equal to target by rotating mat in 90-degree increments any number of times.

Return true if it is possible to make mat equal to target, or false otherwise.

Approach

You can rotate the matrix at most 4 times (including the original orientation), since rotating 4 times brings the matrix back to its original orientation. It’s pointless to rotate more than 4 times.

After each rotation, check if mat is equal to target. If it is, return true. If after 4 rotations it is not equal, return false.

Solution in Python


class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        N = len(mat)

        def rotate(mat):
            for i in range(N):
                for j in range(i + 1, N):
                    mat[i][j], mat[j][i] = mat[j][i], mat[i][j]
            
            for i in range(N):
                mat[i].reverse()

        for i in range(4):
            if mat == target:
                return True
            
            rotate(mat)

        return False

Complexity

  • Time: $O(N^2)$
    Since we rotate the matrix at most 4 times and each rotation takes $O(N^2)$ time.

  • Space: $O(1)$
    Since we do it in-place.

Mistakes I Made

I had to look up the algorithm to rotate the matrix.

I thought of using an extra matrix to store the rotated version but that would have taken $O(N^2)$ space.

And we are done.