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.
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) —
loading...
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