Problem Description

You are given two square binary matrices of the same size: mat and target. Each matrix is n x n in size and contains only 0s and 1s.

Your task is to determine if you can transform mat to exactly match target by rotating mat in 90-degree increments. You can rotate the matrix 0, 1, 2, or 3 times (where 0 rotations means no change, and each rotation is 90 degrees clockwise).

The function should return true if mat can be made equal to target through rotation, and false otherwise.

For example, if you have a 2x2 matrix:

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

After a 90-degree clockwise rotation, it becomes:

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

The solution works by:

1. Checking if mat already equals target (0 rotations)
2. Rotating mat by 90 degrees and checking again
3. Repeating this process up to 4 times total (since 4 rotations of 90 degrees returns to the original position)

The rotation algorithm used in the code performs an in-place rotation by swapping elements in cycles around the matrix. For each layer of the matrix (working from outside to inside), it rotates four elements at a time in a circular pattern.

Intuition

The key insight is that rotating a matrix by 90 degrees clockwise exactly 4 times brings it back to its original position. This creates a cycle: original → 90° → 180° → 270° → 360° (back to original).

Since we want to check if mat can become target through rotation, we only need to check at most 4 positions:

• The original position (0 rotations)
• After 90° rotation (1 rotation)
• After 180° rotation (2 rotations)
• After 270° rotation (3 rotations)

If target matches mat at any of these 4 positions, then we can transform mat into target.

The approach becomes straightforward: keep rotating mat and checking if it equals target after each rotation. If we find a match within 4 rotations, return true. If we've checked all 4 possible orientations without finding a match, return false.

For the rotation itself, we can perform it in-place to save space. The rotation works by moving elements in groups of 4 around the matrix. For a 90-degree clockwise rotation:

• Top row elements move to the right column
• Right column elements move to the bottom row (reversed)
• Bottom row elements move to the left column
• Left column elements move to the top row (reversed)

This cycle of 4 swaps is performed for each "layer" of the matrix, working from the outermost layer inward. The formula matrix[i][j] → matrix[j][n-1-i] captures this transformation mathematically.

Solution Approach

The solution implements a straightforward approach with two main components: a rotation function and a checking loop.

Main Logic: The solution tries all 4 possible rotations of mat and checks if any of them match target:

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

This loop runs exactly 4 times because after 4 rotations of 90 degrees, we're back to the original matrix. If no match is found after checking all 4 orientations, we return false.

In-Place Rotation Algorithm: The rotate function performs a 90-degree clockwise rotation in-place using a layer-by-layer approach:

def rotate(matrix):
    n = len(matrix)
    for i in range(n // 2):
        for j in range(i, n - 1 - i):
            # Perform 4-way swap

The rotation works by processing the matrix in concentric square layers from outside to inside:

• i represents the current layer (0 for outermost, 1 for next inner layer, etc.)
• We only need to process n // 2 layers
• For each layer, we iterate through elements from position i to n - 1 - i

Four-Way Element Swap: For each element in a layer, we perform a cyclic swap of 4 elements:

t = matrix[i][j]                                    # Save top element
matrix[i][j] = matrix[n - j - 1][i]                # Left → Top
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]  # Bottom → Left  
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]  # Right → Bottom
matrix[j][n - i - 1] = t                            # Top → Right

The indices follow the pattern for 90-degree clockwise rotation:

• (i, j) → (j, n-1-i) → (n-1-i, n-1-j) → (n-1-j, i) → back to (i, j)

Time and Space Complexity:

• Time: O(n²) for each rotation × 4 rotations = O(n²)
• Space: O(1) as the rotation is done in-place

The elegance of this solution lies in its simplicity - rather than computing all rotations separately or using complex mathematical transformations, it simply rotates and checks, leveraging the fact that there are only 4 possible orientations to consider.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Given:

• mat = [[0,1],[1,0]]
• target = [[1,0],[0,1]]

Step 1: Check original matrix (0 rotations)

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

Compare: mat ≠ target, so continue.

Step 2: Rotate mat by 90° clockwise

The rotation process for this 2×2 matrix:

• We have 1 layer (since n//2 = 2//2 = 1)
• For layer 0, we process element at position (0,0)
• Perform 4-way swap:
  • Save top: temp = mat[0][0] = 0
  • Left → Top: mat[0][0] = mat[1][0] = 1
  • Bottom → Left: mat[1][0] = mat[1][1] = 0
  • Right → Bottom: mat[1][1] = mat[0][1] = 1
  • Top → Right: mat[0][1] = temp = 0

After rotation:

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

Compare: mat == target ✓ Return true!

Let's trace another example where we need more rotations:

Given:

• mat = [[1,1],[0,1]]
• target = [[1,0],[1,1]]

Iteration 1 (0 rotations):

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

Not equal, rotate.

Iteration 2 (90° rotation): After rotating mat:

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

Not equal, rotate again.

Iteration 3 (180° total rotation): After rotating mat:

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

Compare: mat == target ✓ Return true!

The algorithm found that after 2 rotations (180°), mat matches target.

For a case that returns false, consider:

• mat = [[1,1],[1,1]]
• target = [[0,0],[0,0]]

No matter how many times we rotate a matrix of all 1s, it will never match a matrix of all 0s. After checking all 4 orientations, the algorithm returns false.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm performs at most 4 rotations, and each rotation operation takes O(n²) time where n is the dimension of the square matrix.

Breaking down the rotation function:

• The outer loop runs n/2 times (iterating through layers)
• The inner loop runs approximately n - 2i times for each layer i
• The total number of elements processed is n²/4 (since we process each element exactly once in a 90-degree rotation)
• Each element swap operation takes O(1) time

The comparison mat == target takes O(n²) time as it needs to compare all n² elements.

Since we perform at most 4 rotations and 4 comparisons, the total time complexity is 4 * O(n²) + 4 * O(n²) = O(n²).

Space Complexity: O(1)

The algorithm modifies the matrix in-place without using any additional data structures that scale with input size. Only a constant amount of extra space is used:

• The temporary variable t for swapping elements
• Loop counters i and j
• The variable n storing the matrix dimension

Therefore, the space complexity is O(1) (constant space).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Original Matrix

The most significant pitfall in this solution is that it modifies the input matrix mat in-place during rotation. After the function executes, mat will be left in a rotated state (potentially rotated up to 270 degrees), which can cause unexpected behavior if the caller expects the original matrix to remain unchanged.

Example of the problem:

mat = [[0,1],[1,0]]
target = [[1,0],[0,1]]
solution = Solution()
result = solution.findRotation(mat, target)
print(mat)  # mat is now modified - could be [[1,0],[0,1]] instead of original

Solution: Create a deep copy of the matrix before performing rotations:

def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
    # Create a deep copy to avoid modifying the original
    mat_copy = [row[:] for row in mat]
  
    for _ in range(4):
        if mat_copy == target:
            return True
        rotate_90_clockwise(mat_copy)
    return False

2. Inefficient Comparison After Unnecessary Rotations

The current implementation always rotates the matrix even after the last comparison. If no match is found after checking all 4 orientations, the matrix gets rotated a 4th time unnecessarily (returning it to the original orientation, but still performing unnecessary work).

Solution: Check before rotating on the last iteration:

for i in range(4):
    if mat == target:
        return True
    if i < 3:  # Don't rotate after the last check
        rotate_90_clockwise(mat)
return False

3. Alternative Mathematical Approach Overlooked

While the in-place rotation is space-efficient, for read-only operations or when preserving the original matrix is important, you could use index mapping without modifying the matrix:

Solution using index transformation:

def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
    n = len(mat)
  
    # Check original orientation
    if mat == target:
        return True
  
    # Check 90-degree rotation
    if all(mat[n-1-j][i] == target[i][j] for i in range(n) for j in range(n)):
        return True
  
    # Check 180-degree rotation
    if all(mat[n-1-i][n-1-j] == target[i][j] for i in range(n) for j in range(n)):
        return True
  
    # Check 270-degree rotation
    if all(mat[j][n-1-i] == target[i][j] for i in range(n) for j in range(n)):
        return True
  
    return False

This approach avoids matrix modification entirely and can be more efficient for large matrices since it can short-circuit as soon as a mismatch is found.