algoadvance

You are given two n x n binary matrices mat and target. You are allowed to rotate mat 90 degrees clockwise any number of times. Return true if it is possible to make mat equal to target, or false otherwise.

Example 1:

Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
Output: true
Explanation: We can rotate mat 90 degrees clockwise to make mat equal to target.

Example 2:

Input: mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
Output: false
Explanation: It is impossible to rotate mat to make it equal to target.

Clarifying Questions

1. What is the dimensionality of the matrices?
   • The matrices are n x n, and they are square matrices.
2. Are the elements of the matrices only binary (0s and 1s)?
   • Yes, the matrices contain only binary values.
3. What are the constraints on n (the size of the matrices)?
   • The constraints allow for a reasonable range, suitable for iterative rotations.

Strategy

1. The core idea is to rotate the matrix 90 degrees clockwise up to 3 times (90, 180, 270 degrees) and check if any of the rotated matrices match the target matrix.
2. Define a helper function to perform the 90-degree rotation on the matrix.
3. Compare the resulting matrix from each rotation to the target matrix.
4. If any rotation matches the target matrix, return true. If none match, return false.

Code

def rotate_90(mat):
    n = len(mat)
    rotated = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            rotated[j][n - i - 1] = mat[i][j]
    return rotated

def findRotation(mat, target):
    # We will rotate mat 4 times (0, 90, 180, 270 degrees)
    for _ in range(4):
        if mat == target:
            return True
        mat = rotate_90(mat)
    return False

# Example usage
mat = [[0,1],[1,0]]
target = [[1,0],[0,1]]
print(findRotation(mat, target))  # Output: True

mat = [[0,1],[1,1]]
target = [[1,0],[0,1]]
print(findRotation(mat, target))  # Output: False

Time Complexity

• Rotation Complexity: Each rotation is O(n^2) since we need to rearrange elements in an n x n matrix.
• Comparison Complexity: Each comparison is O(n^2).

Since we perform up to 4 rotations and compare each resulting matrix:

• Overall Time Complexity: O(4 * n^2), which simplifies to O(n^2).

This solution is efficient for the given problem constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?