Determine Whether Matrix Can Be Obtained By Rotation
EasyPrompt
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.lengthn == mat[i].length == target[i].length1 <= n <= 10mat[i][j]andtarget[i][j]are either0or1.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process of rotating the matrix. We generate each of the four possible rotations (0, 90, 180, and 270 degrees) one by one and compare each result with the target matrix. For each rotation, a new auxiliary matrix is created to store the result.
Algorithm
- Create a helper function
areEqual(mat1, mat2)to compare two matrices element by element. It takesO(N^2)time. - Create a helper function
rotate(matrix)that takes a matrix and returns a newN x Nmatrix, which is the 90-degree clockwise rotation of the input. This also takesO(N^2)time and space. - In the main function, start with the original matrix
mat. - In a loop that runs 4 times (for 0, 90, 180, and 270-degree rotations):
- Call
areEqualto compare the current state ofmatwithtarget. If they are equal, returntrue. - If not equal, call
rotateto get the next rotated version of the matrix.
- Call
- If the loop completes without finding a match, return
false.
Walkthrough
The fundamental idea is to check every possible orientation of the mat matrix against the target matrix. A matrix can be rotated 90 degrees clockwise three times before returning to its original state on the fourth rotation. This gives us four states to check.
We can implement this by:
- First, checking if the original
matis equal totarget. - If not, we create a new matrix,
rotated90, by applying the 90-degree rotation formula:rotated[j][n-1-i] = original[i][j]. We then comparerotated90withtarget. - If there's still no match, we rotate
rotated90to getrotated180and compare that withtarget. - Finally, we rotate
rotated180to getrotated270and perform the last comparison.
If any of these comparisons return true, the function returns true. If all four checks fail, it returns false.
class Solution { public boolean findRotation(int[][] mat, int[][] target) { // Check 0 degree rotation if (areEqual(mat, target)) return true; // Check 90, 180, 270 degree rotations int[][] rotatedMat = mat; for (int i = 0; i < 3; i++) { rotatedMat = rotate(rotatedMat); if (areEqual(rotatedMat, target)) { return true; } } return false; } private int[][] rotate(int[][] matrix) { int n = matrix.length; int[][] newMatrix = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { newMatrix[j][n - 1 - i] = matrix[i][j]; } } return newMatrix; } private boolean areEqual(int[][] mat1, int[][] mat2) { int n = mat1.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (mat1[i][j] != mat2[i][j]) { return false; } } } return true; }}Complexity
Time
O(N^2). We perform a constant number of rotations (up to 3) and comparisons (up to 4). Each of these operations takes O(N^2) time to iterate through all the elements of the matrix.
Space
O(N^2), where N is the dimension of the matrix. This is because we create a new N x N matrix to store the result of each rotation.
Trade-offs
Pros
The logic is straightforward and easy to understand as it directly models the physical rotation.
It does not modify the original input matrix.
Cons
Requires extra space proportional to the size of the matrix, which can be inefficient for large matrices.
This approach improves upon the first one by optimizing space. Instead of creating a new matrix for each rotation, we perform the rotation 'in-place', meaning we modify the mat matrix directly. This eliminates the need for O(N^2) auxiliary space.
Algorithm
- Create a helper function
areEqual(mat1, mat2)to compare two matrices, which takesO(N^2)time. - Create a helper function
rotateInPlace(matrix)that rotates the given matrix 90 degrees clockwise without using extra space. This can be done by first transposing the matrix and then reversing each row. - In the main function, loop four times.
- In each iteration, first check if
matis equal totargetusingareEqual. If it is, returntrue. - After the check, call
rotateInPlace(mat)to prepare for the next iteration's check. - If the loop finishes, it means no rotation matched, so return
false.
Walkthrough
The overall logic is the same as the previous approach: check, rotate, and repeat. The key difference is how the rotation is performed. An in-place 90-degree clockwise rotation is a two-step process:
- Transpose the matrix: For each element
mat[i][j], swap it withmat[j][i]. We only need to iterate through the upper or lower triangle of the matrix to avoid swapping elements back to their original place. - Reverse each row: For each row
i, swap the element at columnjwith the element at columnn-1-j, iteratingjfrom0ton/2 - 1.
We can loop four times. In each iteration, we first check for equality with target, and if it fails, we rotate mat in-place for the next check.
class Solution { public boolean findRotation(int[][] mat, int[][] target) { for (int i = 0; i < 4; i++) { if (areEqual(mat, target)) { return true; } rotateInPlace(mat); } return false; } private void rotateInPlace(int[][] matrix) { int n = matrix.length; // Transpose the matrix for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } // Reverse each row for (int i = 0; i < n; i++) { for (int j = 0; j < n / 2; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[i][n - 1 - j]; matrix[i][n - 1 - j] = temp; } } } private boolean areEqual(int[][] mat1, int[][] mat2) { int n = mat1.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (mat1[i][j] != mat2[i][j]) { return false; } } } return true; }}Complexity
Time
O(N^2). The structure is similar to the first approach. We perform a constant number of comparisons and in-place rotations, each taking O(N^2) time.
Space
O(1). The rotation is performed in-place, so no extra space proportional to the input size is required.
Trade-offs
Pros
Highly space-efficient, using only constant extra space.
The time complexity remains optimal at O(N^2).
Cons
This approach modifies the input matrix
mat, which might be undesirable in certain scenarios where the original matrix needs to be preserved.
This is the most efficient approach. Instead of creating new rotated matrices or modifying the input, we can check all four rotation possibilities in a single pass through the matrices. We use mathematical formulas to find the corresponding coordinates in the target matrix for each element in the mat matrix for every possible rotation.
Algorithm
- Initialize four boolean flags,
check0,check90,check180,check270, totrue. - Iterate through the matrix with indices
ifrom0toN-1andjfrom0toN-1. - In each iteration, check the element
mat[i][j]against the corresponding element intargetfor all four possible rotations using index mapping:- 0°:
target[i][j] - 90°:
target[j][N-1-i] - 180°:
target[N-1-i][N-1-j] - 270°:
target[N-1-j][i]
- 0°:
- If a comparison for a specific rotation fails, set its corresponding boolean flag to
false. - After the loops complete, return
trueif any of the four flags is stilltrue, otherwise returnfalse.
Walkthrough
The core of this method lies in understanding the coordinate transformation for each rotation. An element at mat[i][j] moves to a new position depending on the rotation angle. We can check if target is a rotated version of mat by reversing this logic. For example, for target to be a 90-degree clockwise rotation of mat, the element target[j][n-1-i] must be equal to mat[i][j] for all i and j.
The coordinate mappings are:
- 0 degrees:
mat[i][j]corresponds totarget[i][j] - 90 degrees:
mat[i][j]corresponds totarget[j][n-1-i] - 180 degrees:
mat[i][j]corresponds totarget[n-1-i][n-1-j] - 270 degrees:
mat[i][j]corresponds totarget[n-1-j][i]
We can maintain four boolean flags, one for each rotation, initially all true. We then iterate through the matrix once. In each step, we check all four conditions. If a condition is violated, we set the corresponding flag to false. After checking all elements, if at least one flag remains true, it means a valid rotation exists.
class Solution { public boolean findRotation(int[][] mat, int[][] target) { int n = mat.length; boolean c0 = true, c90 = true, c180 = true, c270 = true; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // 0-degree rotation check if (mat[i][j] != target[i][j]) c0 = false; // 90-degree rotation check if (mat[i][j] != target[j][n - 1 - i]) c90 = false; // 180-degree rotation check if (mat[i][j] != target[n - 1 - i][n - 1 - j]) c180 = false; // 270-degree rotation check if (mat[i][j] != target[n - 1 - j][i]) c270 = false; } } return c0 || c90 || c180 || c270; }}Complexity
Time
O(N^2). We iterate through each element of the matrix once. Inside the loop, we perform a constant number of comparisons. This is the optimal time complexity as we must inspect every element at least once.
Space
O(1). We only use a few boolean variables to track the validity of each rotation, which is constant space.
Trade-offs
Pros
Most efficient in terms of both time and space.
Requires only a single pass through the matrices.
Uses constant extra space.
Does not modify the input matrices.
Cons
The index manipulation logic can be slightly more complex to reason about and implement correctly compared to direct simulation.
Solutions
Solution
class Solution {public boolean findRotation(int[][] mat, int[][] target) { int times = 4; while (times-- > 0) { if (equals(mat, target)) { return true; } rotate(mat); } return false; }private void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n / 2; ++i) { for (int j = i; j < n - 1 - i; ++j) { int t = matrix[i][j]; matrix[i][j] = matrix[n - j - 1][i]; matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]; matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]; matrix[j][n - i - 1] = t; } } }private boolean equals(int[][] nums1, int[][] nums2) { int n = nums1.length; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (nums1[i][j] != nums2[i][j]) { return false; } } } return true; }}class Solution {public: bool findRotation(vector<vector<int>> &mat, vector<vector<int>> &target) { int n = mat.size(); for (int k = 0; k < 4; ++k) { vector<vector<int>> g(n, vector<int>(n)); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) g[i][j] = mat[j][n - i - 1]; if (g == target) return true; mat = g; } return false; }};class Solution: def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool: def rotate(matrix): n = len(matrix) for i in range(n // 2): for j in range(i, n - 1 - i): t = matrix[i][j] matrix[i][j] = matrix[n - j - 1][i] matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1] matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1] matrix[j][n - i - 1] = t for _ in range(4): if mat == target: return True rotate(mat) return FalseVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.