LeetCode 1886. Determine Whether Matrix Can Be Obtained By Rotation Solution in Java, C++, Python & More | Explanation + Code

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:

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.

Solutions

Solution 1: In-Place Comparison

We observe the rotation pattern of the matrix and find that for an element mat[i][j], after rotating 90 degrees it appears at position mat[j][n-1-i], after rotating 180 degrees it appears at position mat[n-1-i][n-1-j], and after rotating 270 degrees it appears at position mat[n-1-j][i].

Therefore, we can use an integer ok to record the current rotation state, initialized to 0b1111, indicating that all four rotation states are possible. For each element in the matrix, we compare whether its position under different rotation states matches the corresponding element in the target matrix. If they are not equal, we remove that rotation state from ok. Finally, if ok is not zero, it means at least one rotation state can make the matrix consistent with the target matrix, and we return true; otherwise, we return false.

The time complexity is O(n²), where n is the size of the matrix. The space complexity is O(1).

PythonJavaC++GoTypeScriptRustC#Kotlin

class Solution: def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool: n = len(mat) ok = 0b1111 for i in range(n): for j in range(n): if mat[i][j] != target[i][j]: ok &= ~0b0001 if mat[j][n - 1 - i] != target[i][j]: ok &= ~0b0010 if mat[n - 1 - i][n - 1 - j] != target[i][j]: ok &= ~0b0100 if mat[n - 1 - j][i] != target[i][j]: ok &= ~0b1000 if ok == 0: return False return ok != 0(code-box)

class Solution { public boolean findRotation(int[][] mat, int[][] target) { int n = mat.length; int ok = 0b1111; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (mat[i][j] != target[i][j]) { ok &= ~0b0001; } if (mat[j][n - 1 - i] != target[i][j]) { ok &= ~0b0010; } if (mat[n - 1 - i][n - 1 - j] != target[i][j]) { ok &= ~0b0100; } if (mat[n - 1 - j][i] != target[i][j]) { ok &= ~0b1000; } if (ok == 0) { return false; } } } return ok != 0; } }(code-box)

class Solution { public: bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) { int n = mat.size(); int ok = 0b1111; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (mat[i][j] != target[i][j]) { ok &= ~0b0001; } if (mat[j][n - 1 - i] != target[i][j]) { ok &= ~0b0010; } if (mat[n - 1 - i][n - 1 - j] != target[i][j]) { ok &= ~0b0100; } if (mat[n - 1 - j][i] != target[i][j]) { ok &= ~0b1000; } if (ok == 0) { return false; } } } return ok != 0; } };(code-box)

func findRotation(mat [][]int, target [][]int) bool { n := len(mat) ok := 0b1111 for i := 0; i < n; i++ { for j := 0; j < n; j++ { if mat[i][j] != target[i][j] { ok &= ^0b0001 } if mat[j][n-1-i] != target[i][j] { ok &= ^0b0010 } if mat[n-1-i][n-1-j] != target[i][j] { ok &= ^0b0100 } if mat[n-1-j][i] != target[i][j] { ok &= ^0b1000 } if ok == 0 { return false } } } return ok != 0 }(code-box)

function findRotation(mat: number[][], target: number[][]): boolean { const n = mat.length; let ok = 0b1111; for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (mat[i][j] !== target[i][j]) { ok &= ~0b0001; } if (mat[j][n - 1 - i] !== target[i][j]) { ok &= ~0b0010; } if (mat[n - 1 - i][n - 1 - j] !== target[i][j]) { ok &= ~0b0100; } if (mat[n - 1 - j][i] !== target[i][j]) { ok &= ~0b1000; } if (ok === 0) { return false; } } } return ok !== 0; }(code-box)

impl Solution { pub fn find_rotation(mat: Vec<Vec<i32>>, target: Vec<Vec<i32>>) -> bool { let n = mat.len(); let mut ok: i32 = 0b1111; for i in 0..n { for j in 0..n { if mat[i][j] != target[i][j] { ok &= !0b0001; } if mat[j][n - 1 - i] != target[i][j] { ok &= !0b0010; } if mat[n - 1 - i][n - 1 - j] != target[i][j] { ok &= !0b0100; } if mat[n - 1 - j][i] != target[i][j] { ok &= !0b1000; } if ok == 0 { return false; } } } ok != 0 } }(code-box)

public class Solution { public bool FindRotation(int[][] mat, int[][] target) { int n = mat.Length; int ok = 0b1111; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (mat[i][j] != target[i][j]) { ok &= ~0b0001; } if (mat[j][n - 1 - i] != target[i][j]) { ok &= ~0b0010; } if (mat[n - 1 - i][n - 1 - j] != target[i][j]) { ok &= ~0b0100; } if (mat[n - 1 - j][i] != target[i][j]) { ok &= ~0b1000; } if (ok == 0) { return false; } } } return ok != 0; } }(code-box)

class Solution { fun findRotation(mat: Array<IntArray>, target: Array<IntArray>): Boolean { val n = mat.size var ok = 0b1111 for (i in 0 until n) { for (j in 0 until n) { if (mat[i][j] != target[i][j]) { ok = ok and 0b1110 } if (mat[j][n - 1 - i] != target[i][j]) { ok = ok and 0b1101 } if (mat[n - 1 - i][n - 1 - j] != target[i][j]) { ok = ok and 0b1011 } if (mat[n - 1 - j][i] != target[i][j]) { ok = ok and 0b0111 } if (ok == 0) { return false } } } return ok != 0 } }(code-box)