Algorithms to Determine Whether Matrix Can Be Obtained By Rotation


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.

rotate-matrix Algorithms to Determine Whether Matrix Can Be Obtained By Rotation algorithms c / c++ math python

Hints:
What is the maximum number of rotations you have to check?
Is there a formula you can use to rotate a matrix 90 degrees?

C++ Rotate and Check

We can define a function to rotate a matrix by 90 degree clockwise: first transpose the matrix, and then reverse each row. And then, just need to check at most four rotations:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
        function<void(vector<vector<int>>&)> rotate = [](vector<vector<int>>& M) {
            int rows = static_cast<int>(M.size());
            int cols = static_cast<int>(M[0].size());
            // transpose the matrix
            for (int i = 0; i < rows; ++ i) {
                for (int j = 0; j < i; ++ j) {
                    swap(M[i][j], M[j][i]);
                }
            }
            // then reverse each row
            for_each(begin(M), end(M), [](auto &a) {
                reverse(begin(a), end(a));
            });
        };
        for (int i = 0; i < 4; ++ i) {
            if (mat == target) return true;
            rotate(mat);
        }
        return false;
    }
};
class Solution {
public:
    bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
        function<void(vector<vector<int>>&)> rotate = [](vector<vector<int>>& M) {
            int rows = static_cast<int>(M.size());
            int cols = static_cast<int>(M[0].size());
            // transpose the matrix
            for (int i = 0; i < rows; ++ i) {
                for (int j = 0; j < i; ++ j) {
                    swap(M[i][j], M[j][i]);
                }
            }
            // then reverse each row
            for_each(begin(M), end(M), [](auto &a) {
                reverse(begin(a), end(a));
            });
        };
        for (int i = 0; i < 4; ++ i) {
            if (mat == target) return true;
            rotate(mat);
        }
        return false;
    }
};

Here, we use the std::for_each to reverse each row of the matrix. The time complexity is O(NM) where N and M are the number of the rows and cols of the matrix. The rotation is done in place and thus the space complexity is O(1).

Rotate and Check Matrix in Python

In Python, we can use the [::-1] to reverse a vector.

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:
        def rotate(M):
            if not M:
                return M
            rows, cols = len(M), len(M[0])
            for i in range(rows):
                for j in range(i):
                    M[i][j], M[j][i] = M[j][i], M[i][j]
            for i in range(rows):
                M[i] = M[i][::-1]
            return M
        for i in range(4):
            if mat == target:
                return True
            rotate(mat)
        return False
class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        def rotate(M):
            if not M:
                return M
            rows, cols = len(M), len(M[0])
            for i in range(rows):
                for j in range(i):
                    M[i][j], M[j][i] = M[j][i], M[i][j]
            for i in range(rows):
                M[i] = M[i][::-1]
            return M
        for i in range(4):
            if mat == target:
                return True
            rotate(mat)
        return False

Same time and space complexity. The transpose + reverse makes a rotation.

See also: Teaching Kids Programming – Rotate a 2D Matrix/Image 90 Degree Clockwise

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
531 words
Last Post: Teaching Kids Programming - Depth First Search Algorithm to Count the Vertical Lines in Binary Tree
Next Post: Teaching Kids Programming - Sign of the Product of an Array

The Permanent URL is: Algorithms to Determine Whether Matrix Can Be Obtained By Rotation

Leave a Reply