Scale Engineer

Determine Whether Matrix Can Be Obtained By Rotation

Easy
#1722Time: O(N^2). We perform a constant number of rotations (up to 3) and comparisons (up to 4). Each of these operations takes O(N^2) time to iterate through all the elements of the matrix.Space: O(N^2), where N is the dimension of the matrix. This is because we create a new N x N matrix to store the result of each rotation.
Data structures
ArrayMatrix

Prompt

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.

 

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 target.

Example 2:

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

Example 3:

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

 

Constraints:

  • n == mat.length == target.length
  • n == mat[i].length == target[i].length
  • 1 <= n <= 10
  • mat[i][j] and target[i][j] are either 0 or 1.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process of rotating the matrix. We generate each of the four possible rotations (0, 90, 180, and 270 degrees) one by one and compare each result with the target matrix. For each rotation, a new auxiliary matrix is created to store the result.

Algorithm

  • Create a helper function areEqual(mat1, mat2) to compare two matrices element by element. It takes O(N^2) time.
  • Create a helper function rotate(matrix) that takes a matrix and returns a new N x N matrix, which is the 90-degree clockwise rotation of the input. This also takes O(N^2) time and space.
  • In the main function, start with the original matrix mat.
  • In a loop that runs 4 times (for 0, 90, 180, and 270-degree rotations):
    1. Call areEqual to compare the current state of mat with target. If they are equal, return true.
    2. If not equal, call rotate to get the next rotated version of the matrix.
  • If the loop completes without finding a match, return false.

Walkthrough

The fundamental idea is to check every possible orientation of the mat matrix against the target matrix. A matrix can be rotated 90 degrees clockwise three times before returning to its original state on the fourth rotation. This gives us four states to check.

We can implement this by:

  1. First, checking if the original mat is equal to target.
  2. If not, we create a new matrix, rotated90, by applying the 90-degree rotation formula: rotated[j][n-1-i] = original[i][j]. We then compare rotated90 with target.
  3. If there's still no match, we rotate rotated90 to get rotated180 and compare that with target.
  4. Finally, we rotate rotated180 to get rotated270 and perform the last comparison.

If any of these comparisons return true, the function returns true. If all four checks fail, it returns false.

class Solution {    public boolean findRotation(int[][] mat, int[][] target) {        // Check 0 degree rotation        if (areEqual(mat, target)) return true;                // Check 90, 180, 270 degree rotations        int[][] rotatedMat = mat;        for (int i = 0; i < 3; i++) {            rotatedMat = rotate(rotatedMat);            if (areEqual(rotatedMat, target)) {                return true;            }        }                return false;    }     private int[][] rotate(int[][] matrix) {        int n = matrix.length;        int[][] newMatrix = new int[n][n];        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                newMatrix[j][n - 1 - i] = matrix[i][j];            }        }        return newMatrix;    }     private boolean areEqual(int[][] mat1, int[][] mat2) {        int n = mat1.length;        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                if (mat1[i][j] != mat2[i][j]) {                    return false;                }            }        }        return true;    }}

Complexity

Time

O(N^2). We perform a constant number of rotations (up to 3) and comparisons (up to 4). Each of these operations takes O(N^2) time to iterate through all the elements of the matrix.

Space

O(N^2), where N is the dimension of the matrix. This is because we create a new N x N matrix to store the result of each rotation.

Trade-offs

Pros

  • The logic is straightforward and easy to understand as it directly models the physical rotation.

  • It does not modify the original input matrix.

Cons

  • Requires extra space proportional to the size of the matrix, which can be inefficient for large matrices.

Solutions

class Solution {public  boolean findRotation(int[][] mat, int[][] target) {    int times = 4;    while (times-- > 0) {      if (equals(mat, target)) {        return true;      }      rotate(mat);    }    return false;  }private  void rotate(int[][] matrix) {    int n = matrix.length;    for (int i = 0; i < n / 2; ++i) {      for (int j = i; j < n - 1 - i; ++j) {        int t = matrix[i][j];        matrix[i][j] = matrix[n - j - 1][i];        matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];        matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];        matrix[j][n - i - 1] = t;      }    }  }private  boolean equals(int[][] nums1, int[][] nums2) {    int n = nums1.length;    for (int i = 0; i < n; ++i) {      for (int j = 0; j < n; ++j) {        if (nums1[i][j] != nums2[i][j]) {          return false;        }      }    }    return true;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem