LeetCode 1886 - Determine Whether Matrix Can Be Obtained By Rotation

LeetCode Problem 1886

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Problem Understanding

The problem gives us two square binary matrices, mat and target, both of size n x n. Each cell contains either 0 or 1. Our task is to determine whether mat can be transformed into target by rotating it clockwise in 90 degree increments.

A rotation can be performed multiple times. Since rotating a square matrix four times returns it to its original orientation, there are only four possible states we need to consider:

1. No rotation, 0 degrees
2. One rotation, 90 degrees
3. Two rotations, 180 degrees
4. Three rotations, 270 degrees

If any of these rotated versions matches target, we return true. Otherwise, we return false.

The matrices are guaranteed to be square, and the size constraint is very small:

• 1 <= n <= 10

This small constraint tells us that efficiency is not a major concern. Even an algorithm with cubic complexity would comfortably pass. However, we still want a clean and logically optimal solution.

An important detail is that the matrix elements are binary, but that fact does not fundamentally change the algorithm. The same logic would work for any values.

Some important edge cases include:

• A 1 x 1 matrix, where rotation does nothing.
• Matrices that already match without any rotation.
• Matrices that only match after multiple rotations.
• Matrices that never match.
• Symmetric matrices, where multiple rotations may produce the same matrix.

Because the input is guaranteed to be valid square matrices of equal dimensions, we do not need to handle malformed input.

Approaches

Brute Force Approach

The brute force strategy is straightforward. We repeatedly rotate the matrix and compare it with target.

The algorithm works as follows:

1. Compare mat with target.
2. If they match, return true.
3. Otherwise, rotate mat clockwise by 90 degrees.
4. Repeat this process up to four times.

Since there are only four possible orientations, this guarantees that we examine every valid rotation.

To rotate a matrix, we create a new matrix where each element is repositioned according to the rotation rule:

new[j][n - 1 - i] = old[i][j]

Each rotation requires visiting every cell, which costs O(n^2). Each comparison also costs O(n^2). Since we do this at most four times, the total work remains manageable.

This approach is already efficient enough for the problem constraints.

Key Insight for the Optimal Solution

The key observation is that a square matrix has only four unique rotational states. We do not need any advanced search or simulation.

Instead of trying arbitrary transformations, we can systematically generate each rotated version and directly compare it to the target matrix.

Because the number of rotations is constant, the complexity effectively remains proportional to the number of matrix cells.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4 × n²)	O(n²)	Rotate and compare up to four times
Optimal	O(n²)	O(n²)	Same practical approach, since rotations are bounded by four

Although both rows appear similar, the second framing emphasizes the important observation that the number of rotations is constant.

Algorithm Walkthrough

1. Start with the original matrix mat.
2. Compare the current matrix with target.

This check determines whether the current orientation already matches the desired matrix. If they are equal, we can immediately return True. 3. If the matrices do not match, rotate the matrix clockwise by 90 degrees.

For every position (i, j) in the original matrix, place its value into position (j, n - 1 - i) in the rotated matrix. 4. Replace the current matrix with the rotated version.

This allows the next iteration to continue rotating from the current orientation. 5. Repeat the process four times.

Four rotations cover all possible orientations:

• 0 degrees
• 90 degrees
• 180 degrees
• 270 degrees

6. If none of the rotations match target, return False.

Why it works

A square matrix rotated clockwise repeatedly cycles through exactly four possible orientations before returning to its original state. Therefore, checking all four rotations guarantees that we examine every possible valid transformation. If none match the target matrix, then no valid rotation exists.

Python Solution

from typing import List

class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        def rotate(matrix: List[List[int]]) -> List[List[int]]:
            n = len(matrix)
            rotated = [[0] * n for _ in range(n)]

            for i in range(n):
                for j in range(n):
                    rotated[j][n - 1 - i] = matrix[i][j]

            return rotated

        current = mat

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

            current = rotate(current)

        return False

The implementation begins by defining a helper function called rotate. This function constructs a new matrix of the same size and fills it according to the clockwise rotation mapping.

The expression:

rotated[j][n - 1 - i] = matrix[i][j]

is the core transformation rule for clockwise rotation.

The variable current stores the current orientation of the matrix. Initially, it references the original mat.

The loop runs four times because there are only four possible rotations. During each iteration:

1. The current matrix is compared with target.
2. If they are equal, the function immediately returns True.
3. Otherwise, the matrix is rotated once for the next iteration.

If all four orientations fail to match, the function returns False.

Go Solution

func findRotation(mat [][]int, target [][]int) bool {
    rotate := func(matrix [][]int) [][]int {
        n := len(matrix)

        rotated := make([][]int, n)
        for i := 0; i < n; i++ {
            rotated[i] = make([]int, n)
        }

        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                rotated[j][n-1-i] = matrix[i][j]
            }
        }

        return rotated
    }

    isEqual := func(a [][]int, b [][]int) bool {
        n := len(a)

        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if a[i][j] != b[i][j] {
                    return false
                }
            }
        }

        return true
    }

    current := mat

    for k := 0; k < 4; k++ {
        if isEqual(current, target) {
            return true
        }

        current = rotate(current)
    }

    return false
}

The Go solution follows the same logic as the Python implementation, but there are some language specific differences.

Go does not support direct matrix equality comparison for slices, so we define an explicit isEqual helper function that compares each cell manually.

Matrix allocation also requires explicit initialization using make.

The rotation logic itself is identical to the Python version.

Since matrix sizes are very small, there are no concerns about memory usage or integer overflow.

Worked Examples

Example 1

mat =
[
  [0,1],
  [1,0]
]

target =
[
  [1,0],
  [0,1]
]

Initial state:

Rotation	Matrix	Matches Target
0 degrees	[[0,1],[1,0]]	No

Rotate 90 degrees clockwise.

Transformation steps:

Original Position	Value	New Position
(0,0)	0	(0,1)
(0,1)	1	(1,1)
(1,0)	1	(0,0)
(1,1)	0	(1,0)

Resulting matrix:

[
  [1,0],
  [0,1]
]

This matches target, so we return True.

Example 2

mat =
[
  [0,1],
  [1,1]
]

target =
[
  [1,0],
  [0,1]
]

Check all four rotations:

Rotation	Matrix	Match
0 degrees	[[0,1],[1,1]]	No
90 degrees	[[1,0],[1,1]]	No
180 degrees	[[1,1],[1,0]]	No
270 degrees	[[1,1],[0,1]]	No

None match the target matrix, so we return False.

Example 3

mat =
[
  [0,0,0],
  [0,1,0],
  [1,1,1]
]

After the first rotation:

[
  [1,0,0],
  [1,1,0],
  [1,0,0]
]

No match yet.

After the second rotation:

[
  [1,1,1],
  [0,1,0],
  [0,0,0]
]

This equals target, so the algorithm returns True.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	At most four rotations and comparisons
Space	O(n²)	Extra matrix created during rotation

The algorithm performs a constant number of operations on every matrix cell. Since the number of rotations is fixed at four, the constant factor does not affect asymptotic complexity.

The additional space comes from constructing a rotated matrix during each transformation.

Test Cases

from typing import List

class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        def rotate(matrix):
            n = len(matrix)
            rotated = [[0] * n for _ in range(n)]

            for i in range(n):
                for j in range(n):
                    rotated[j][n - 1 - i] = matrix[i][j]

            return rotated

        current = mat

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

            current = rotate(current)

        return False

sol = Solution()

# Example 1, matches after one rotation
assert sol.findRotation([[0,1],[1,0]], [[1,0],[0,1]]) == True

# Example 2, impossible to match
assert sol.findRotation([[0,1],[1,1]], [[1,0],[0,1]]) == False

# Example 3, matches after two rotations
assert sol.findRotation(
    [[0,0,0],[0,1,0],[1,1,1]],
    [[1,1,1],[0,1,0],[0,0,0]]
) == True

# Already equal without rotation
assert sol.findRotation([[1]], [[1]]) == True

# Single element mismatch
assert sol.findRotation([[0]], [[1]]) == False

# Matches after three rotations
assert sol.findRotation(
    [[1,0],[0,0]],
    [[0,1],[0,0]]
) == True

# Symmetric matrix remains same after rotation
assert sol.findRotation(
    [[1,0],[0,1]],
    [[1,0],[0,1]]
) == True

# Larger matrix with no valid rotation
assert sol.findRotation(
    [[1,0,0],[0,1,0],[0,0,1]],
    [[0,1,0],[1,0,0],[0,0,1]]
) == False

Test Summary

Test	Why
Example 1	Validates single rotation case
Example 2	Validates impossible transformation
Example 3	Validates multiple rotations
[[1]] vs [[1]]	Smallest valid matrix
[[0]] vs [[1]]	Single cell mismatch
Three rotation case	Ensures all four rotations are checked
Symmetric matrix	Validates no rotation needed
Larger mismatch case	Ensures false negatives are avoided

Edge Cases

One important edge case is a 1 x 1 matrix. Since rotating a single element matrix changes nothing, the algorithm must correctly identify whether the two values already match. The implementation handles this naturally because all rotations produce the same matrix.

Another important case is when the matrices are already equal before any rotation occurs. A buggy implementation might rotate first and miss this scenario. Our solution checks equality before each rotation, including the original orientation.

A third important edge case involves symmetric matrices. Some matrices remain unchanged after one or more rotations. For example:

[
  [1,0],
  [0,1]
]

may appear identical under certain transformations. The implementation correctly handles this because it simply compares matrices at every stage without assuming uniqueness between rotations.

A final subtle edge case occurs when the correct answer requires exactly three rotations, 270 degrees clockwise. Some incorrect implementations only check one or two rotations. By iterating exactly four times, our solution guarantees that every valid orientation is examined.