Determine Whether Matrix Can Be Obtained By Rotation

You are given two n x n binary matrices, mat and target. Return true if you can make mat equal to target by rotating mat in 90-degree increments. You can rotate zero, one, two, or three times.

This is LeetCode 1886: Determine Whether Matrix Can Be Obtained By Rotation. It is a nice entry point into matrix rotation problems because the solution is short and the pattern is reusable.

Why this problem matters

Matrix rotation is one of those operations that shows up across many problems. Understanding how to rotate a grid 90 degrees clockwise is useful for image processing questions, game board transformations, and spatial reasoning problems in general. This problem gives you a low-pressure way to practice the rotation mechanic because you do not need to do it in place. You just need to check whether any rotation matches the target.

Once you can rotate a matrix confidently, problems like Rotate Image (LeetCode 48) and Spiral Matrix (LeetCode 54) feel much less intimidating.

The brute force approach

The most direct approach is to generate all four rotations of mat and check whether any of them equals target. You can generate a rotated copy of the matrix each time and compare it element by element.

def findRotation(mat, target):
    n = len(mat)
    current = [row[:] for row in mat]
    for _ in range(4):
        if current == target:
            return True
        rotated = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                rotated[j][n - 1 - i] = current[i][j]
        current = rotated
    return False

This works and is perfectly fine for this problem. But you can simplify the rotation step by using a well-known trick.

The key insight: rotate = transpose + reverse rows

A 90-degree clockwise rotation can be decomposed into two operations:

1. Transpose the matrix (swap rows and columns, so element at (i, j) moves to (j, i))
2. Reverse each row

Why does this work? After transposing, the element originally at (r, c) sits at (c, r). Reversing row c then moves it from column r to column n - 1 - r. The final position is (c, n - 1 - r), which is exactly where a 90-degree clockwise rotation places it.

For this problem, you do not even need in-place rotation. You can use a one-liner list comprehension to produce the rotated matrix.

Walking through it step by step

Let's trace through the example with mat = [[0,1],[1,0]] and target = [[1,0],[0,1]]. We check each of the four possible rotations.

At 0 degrees (the original matrix), mat is [[0,1],[1,0]], which does not equal target. After one 90-degree rotation, mat becomes [[1,0],[0,1]], which matches target exactly. We can stop here and return true. The 180 and 270 degree rotations are shown for completeness. Notice that for this particular matrix (a 2x2 anti-diagonal pattern), both 90 and 270 degree rotations produce the same result.

The complete solution

def findRotation(mat, target):
    def rotate(m):
        n = len(m)
        return [[m[n - 1 - j][i] for j in range(n)] for i in range(n)]

    current = mat
    for _ in range(4):
        if current == target:
            return True
        current = rotate(current)
    return False

The rotate function builds a new matrix where each element (i, j) is taken from position (n - 1 - j, i) in the original. This is equivalent to the transpose-then-reverse approach but expressed as a single comprehension.

The main loop checks the current state against target, then rotates. It runs up to four times, covering 0, 90, 180, and 270 degrees. If none of them match, we return False.

Complexity analysis

Time: Each rotation visits all n^2 elements, and each comparison visits all n^2 elements. We do this at most four times, so the total is 4 * O(n^2) = O(n^2).

Space: We create a new n x n matrix for each rotation. You could optimize this to O(1) extra space by comparing elements in place using the rotation formula directly, but for this problem the simpler approach is fine.

Building blocks

Matrix rotation pattern

The ability to rotate a matrix 90 degrees clockwise is the core building block here. The formula rotated[i][j] = original[n - 1 - j][i] maps every element to its rotated position. This same pattern drives Rotate Image (LeetCode 48), and once you know it, you can rotate in any direction by adjusting the index mapping.

In-place transpose

Transposing a matrix (swapping matrix[i][j] with matrix[j][i]) is a fundamental operation that appears in rotation, reflection, and many linear algebra problems. Even though this problem does not require in-place work, understanding transpose helps you decompose spatial transformations into manageable steps.

Edge cases

• 1x1 matrix: A single element always matches itself regardless of rotation. mat = [[1]], target = [[1]] returns true.
• Already equal: If mat already equals target with no rotation, the first iteration catches it.
• No rotation matches: mat = [[0,0],[0,1]] and target = [[1,1],[0,0]] returns false because no rotation of mat can produce target.
• All zeros or all ones: Any rotation of an all-zeros matrix is still all zeros. If target is also all zeros, return true. Same for all ones.
• Larger matrices: The approach scales to any n. For a 10x10 matrix, you still only need four rotation checks.
• Symmetric matrices: Some matrices look the same after certain rotations. For example, the identity pattern is unchanged by 180-degree rotation. The algorithm handles this naturally since it checks equality at each step.

Common mistakes

1. Forgetting the 0-degree check. If mat already equals target, you should return true immediately. Some people only check after rotating, missing the case where no rotation is needed.

2. Rotating in the wrong direction. There are different index formulas for clockwise vs. counterclockwise rotation. Using rotated[i][j] = original[j][n - 1 - i] gives you counterclockwise. The distinction does not matter for this problem (checking all four rotations covers both directions), but it matters when you need a specific rotation direction.

3. Mutating the original matrix. If you rotate mat in place and the problem expects the original mat to be unchanged afterward, you could corrupt the input. Using a copy or building a new matrix avoids this.

4. Off-by-one in the rotation formula. Writing n - j instead of n - 1 - j shifts every element by one position, producing incorrect results. Since indices are zero-based, the correct offset is n - 1.

From understanding to recall

You now know how to check all four rotations of a matrix against a target. The core idea is small: rotate, compare, repeat. But the rotation formula itself, rotated[i][j] = original[n - 1 - j][i], has enough index arithmetic that it is easy to second-guess under pressure.

Spaced repetition helps you internalize the rotation mapping until it becomes automatic. You write the rotate function from scratch, verify it against a 2x2 example, and move on. A few days later you do it again. After a handful of reps, you see "matrix rotation" and the index formula appears without hesitation.

Matrix rotation is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning it in isolation and drilling it with spaced repetition is far more effective than re-deriving the formula every time you encounter a new matrix problem.

Related posts

• Rotate Image - The classic in-place matrix rotation problem
• Spiral Matrix - Another matrix traversal pattern
• Valid Sudoku - Grid-based constraint checking

CodeBricks breaks this problem into its rotation building block and drills it independently with spaced repetition. You type the rotation formula from scratch until it sticks. When a matrix rotation problem shows up in your interview, you write the solution without pausing to rethink the index math.