Determine Whether Matrix Can Be Obtained By Rotation

Ah, the classic problem of determining whether one matrix can be obtained from another by rotation. It’s like trying to figure out if your friend’s jigsaw puzzle piece can fit into yours after a few spins. Spoiler alert: sometimes it can, and sometimes it just can’t, no matter how hard you try!

Imagine you’re at a party, and you see someone trying to fit a square peg into a round hole. You can’t help but chuckle, thinking, “If only they could rotate that peg!” Well, that’s exactly what we’re doing here with matrices.

Problem Description

The problem is simple yet perplexing: Given two matrices, mat and target, you need to determine if you can rotate mat by 90 degrees (up to three times) to make it equal to target. It’s like trying to convince your stubborn friend that their favorite pizza topping (pineapple, anyone?) can actually be delicious if you just rotate it a bit.

Solution in Java


class Solution {
  public boolean findRotation(int[][] mat, int[][] target) {
    for (int i = 0; i < 4; ++i) {
      if (Arrays.deepEquals(mat, target))
        return true;
      rotate(mat);
    }
    return false;
  }

  private void rotate(int[][] mat) {
    for (int i = 0, j = mat.length - 1; i < j; ++i, --j) {
      int[] temp = mat[i];
      mat[i] = mat[j];
      mat[j] = temp;
    }
    for (int i = 0; i < mat.length; ++i)
      for (int j = i + 1; j < mat.length; ++j) {
        final int temp = mat[i][j];
        mat[i][j] = mat[j][i];
        mat[j][i] = temp;
      }
  }
}

Approach

The approach is straightforward: we check if the mat matrix matches the target matrix after each 90-degree rotation. We do this up to three times (because four rotations bring us back to the original position). The rotate method handles the actual rotation of the matrix by first flipping it vertically and then transposing it.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N^2)
Space Complexity	O(1)

Real-World Example

Think of it this way: you’re at a dance party, and you want to see if you can get your dance moves to match your friend’s. You try rotating your body (or your dance style) to see if you can sync up. Sometimes it works, and sometimes you just end up looking like a confused octopus. Similarly, with matrices, sometimes they can be rotated to match, and sometimes they just can’t!