We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Determine Whether Matrix Can Be Obtained By Rotation

Number: 2015

Difficulty: Easy

Paid? No

Companies: Meta, Google, Amazon

Problem Description

Given two n x n binary matrices mat and target, determine whether it is possible to make mat equal to target by rotating mat in 90-degree increments. Return true if mat can be rotated to match target, otherwise return false.

Key Insights

  • You can rotate the matrix in 90-degree increments (0, 90, 180, and 270 degrees).
  • The matrix rotation can be achieved by first transposing the matrix and then reversing each row.
  • Since the matrix size is small (n <= 10), checking all four rotations using brute force is efficient.
  • Compare the rotated matrix after each rotation with the target matrix.

Space and Time Complexity

Time Complexity: O(n^2) per rotation, overall O(4*n^2) which simplifies to O(n^2).
Space Complexity: O(n^2) if an extra matrix is used for the rotation; can potentially be reduced with an in-place rotation technique.

Solution

The solution works by rotating the matrix four times (including the original orientation) and checking if the rotated matrix matches the target after each rotation. The rotation is performed by transposing the matrix (swapping rows and columns) and then reversing each row, which effectively rotates the matrix by 90 degrees clockwise. If any of the four rotations result in a matrix that is equal to the target, the function returns true; otherwise, it returns false.

Code Solutions

# Python solution
def findRotation(mat, target):
    # Helper function to rotate a matrix 90 degrees clockwise
    def rotate(matrix):
        # Transpose the matrix and reverse each row to achieve rotation
        return [list(row)[::-1] for row in zip(*matrix)]
    
    # Try up to four rotations (0, 90, 180, and 270 degrees)
    for _ in range(4):
        if mat == target:
            return True
        mat = rotate(mat)
    return False

# Example usage:
if __name__ == "__main__":
    mat = [[0, 1], [1, 0]]
    target = [[1, 0], [0, 1]]
    print(findRotation(mat, target))  # Output: True
← Back to All Questions