Skip to content

1886. Determine Whether Matrix Can Be Obtained By Rotation

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 \(\text{mat}[i][j]\), after rotating 90 degrees it appears at position \(\text{mat}[j][n-1-i]\), after rotating 180 degrees it appears at position \(\text{mat}[n-1-i][n-1-j]\), and after rotating 270 degrees it appears at position \(\text{mat}[n-1-j][i]\).

Therefore, we can use an integer \(\textit{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 \(\textit{ok}\). Finally, if \(\textit{ok}\) is not zero, it means at least one rotation state can make the matrix consistent with the target matrix, and we return \(\textit{true}\); otherwise, we return \(\textit{false}\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
    }
}

Comments