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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Determine Whether Matrix Can Be Obtained By Rotation

Difficulty: Easy

Problem Description

Given two n x n binary matrices mat and target, return true if it is possible to make mat equal to target by rotating mat in 90-degree increments, or false otherwise.

Key Insights

  • The problem is about comparing the original matrix with its rotated versions.
  • A matrix can be rotated four times (0 degrees, 90 degrees, 180 degrees, and 270 degrees).
  • Each rotation can be achieved by manipulating the indices of the matrix elements.
  • The constraints ensure that the matrices are small (1 <= n <= 10), making exhaustive checks feasible.

Space and Time Complexity

Time Complexity: O(n^2) - We need to check each element of the matrix for all four rotations. Space Complexity: O(1) - We can perform rotations in place without needing additional space proportional to input size.

Solution

To solve this problem, we can create a function that rotates the matrix by 90 degrees clockwise. We will then compare the original matrix with its rotated versions (0, 90, 180, and 270 degrees). If any of the rotated matrices match the target matrix, we return true; otherwise, we return false.

The algorithmic approach involves:

  1. Rotating the matrix.
  2. Checking if the rotated matrix is equal to the target.
  3. Repeating the process for all four possible rotations.

Code Solutions

def rotate(matrix):
    n = len(matrix)
    # Transpose the matrix
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row
    for i in range(n):
        matrix[i].reverse()

def canBeObtainedByRotation(mat, target):
    for _ in range(4):
        if mat == target:
            return True
        rotate(mat)  # Rotate the matrix by 90 degrees
    return False
← Back to All Questions