Determine Whether Matrix Can Be Obtained By Rotation - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: You are given two n x n matrices: mat and target. The task is to determine whether rotating mat by 0°, 90°, 180°, or 270° clockwise can make it exactly equal to target. Each rotation transforms element positions while preserving matrix size.
Approach 1: Rotate and Compare (Time: O(n2), Space: O(1))
Simulate the rotation process directly and compare the matrix with target after each rotation. A 90° clockwise rotation maps mat[i][j] to mat[j][n-1-i]. Rotate the matrix up to four times and after each rotation iterate through all cells to check if the matrices match. Each comparison takes O(n^2), and since there are at most four rotations, the overall complexity remains O(n^2). This approach works well because the rotation count is constant, so the algorithm stays efficient even for larger matrices.
Approach 2: Precompute 4 Rotations (Time: O(n2), Space: O(n2))
Instead of modifying the original matrix, generate all four rotated versions and compare each with target. Compute the 90°, 180°, and 270° transformations using index mapping while storing results in temporary matrices. After generating each rotation, perform a full matrix comparison. This approach is slightly easier to reason about because every rotation is stored explicitly, but it uses additional memory for the intermediate matrices.
Both approaches rely on understanding how indices move during a 90° clockwise rotation in a square matrix. This pattern frequently appears in problems involving matrix manipulation and array traversal, especially when dealing with grid transformations or image rotations.
Recommended for interviews: The rotate-and-compare approach is typically preferred. It demonstrates that you understand the coordinate transformation for matrix rotation and can implement it efficiently with constant extra space. Precomputing rotations is still acceptable and can help when you want clearer logic during implementation.
Approach 1: Rotate and Compare
This approach involves rotating the matrix and comparing it with the target matrix for each rotation position.
We start by comparing the original matrix with the target. If they are equal, return true. Otherwise, repeat the process for the matrix rotated 90, 180, and 270 degrees clockwise. The rotation is handled by transposing the matrix and then reversing each row.
This solution defines a helper function to compare two matrices and a function to rotate a matrix 90 degrees clockwise. We check if the matrix is equal to the target initially, and after each rotation, up to four rotations (including zero rotations).
Complexity
Time Complexity: O(n^2)
Space Complexity: O(1), as we are modifying the matrix in place and using only a constant amount of extra space.
Approach 2: Precompute 4 Rotations
This approach precomputes all four rotations (0, 90, 180, 270 degrees) of the given matrix and directly checks them against the target matrix to see if any match. We define a function to perform matrix transposition and reversing of rows to perform rotation.
This precomputation method uses two helper functions to transpose and reverse columns of the matrix to generate all possible rotations in a precomputed fashion. We then simply check each precomputed rotation against the target matrix for a match.
Complexity
Time Complexity: O(n^2)
Space Complexity: O(1), in-place modification of existing matrices only.
Approach 3: 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^2), where n is the size of the matrix. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Rotate and Compare | Time Complexity: O(n^2) Space Complexity: O(1), as we are modifying the matrix in place and using only a constant amount of extra space. |
| Precompute 4 Rotations | Time Complexity: O(n^2) Space Complexity: O(1), in-place modification of existing matrices only. |
| In-Place Comparison | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Rotate and Compare | O(n^2) | O(1) | Best general solution when you want minimal memory usage and direct rotation simulation. |
| Precompute 4 Rotations | O(n^2) | O(n^2) | Useful when clearer logic is preferred or when storing rotated matrices simplifies comparison. |
Video Solution
Determine Whether Matrix Can Be Obtained By Rotation | Simple Detailed | Leetcode 1886 | MIK • codestorywithMIK • 6,571 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Determine Whether Matrix Can Be Obtained By Rotation easy or hard?
Determine Whether Matrix Can Be Obtained By Rotation Python/Java solution
How to solve Determine Whether Matrix Can Be Obtained By Rotation in O(n^2)?
What is the best approach for Determine Whether Matrix Can Be Obtained By Rotation?
Is Determine Whether Matrix Can Be Obtained By Rotation asked at Google/Amazon/Meta?
What data structure is used in Determine Whether Matrix Can Be Obtained By Rotation?
What is the time complexity of Determine Whether Matrix Can Be Obtained By Rotation?
Ready to solve this problem?
Practice Determine Whether Matrix Can Be Obtained By Rotation with our built-in code editor and test cases.
Practice on FleetCode