Formatted question description: https://leetcode.ca/all/1886.html

1886. Determine Whether Matrix Can Be Obtained By Rotation

Level

Easy

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.

Example 1:

Image text

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:

Image text

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:

Image text

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.

Solution

Let rotate be the state of mat after rotating 90 degrees clockwise. For 0 <= i < n and 0 <= j < n, there is rotate[j][n - 1 - i] = mat[i][j]. Since rotating the matrix 4 times makes the matrix recover to the original state, the matrix can be rotated at most 4 times. Therefore, rotate the matrix 1, 2, 3 and 4 times respecitvely, and for each state, check whether the state is the same as target. If there exists one state that is the same as target, return true. Otherwise, return false.

class Solution {
    public boolean findRotation(int[][] mat, int[][] target) {
        int n = mat.length;
        int[][] rotate = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                rotate[i][j] = mat[i][j];
        }
        for (int count = 1; count <= 4; count++) {
            int[][] temp = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    temp[j][n - 1 - i] = rotate[i][j];
            }
            rotate = temp;
            if (areSame(rotate, target))
                return true;
        }
        return false;
    }

    public boolean areSame(int[][] mat, int[][] target) {
        int n = mat.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] != target[i][j])
                    return false;
            }
        }
        return true;
    }
}

All Problems

All Solutions