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] and target[i][j] are either 0 or 1.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).
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2)
Space Complexity: O(1), in-place modification of existing matrices only.
| 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. |
Rotate Matrix/Image by 90 Degrees | Brute - Optimal • take U forward • 324,764 views views
Watch 9 more video solutions →Practice Determine Whether Matrix Can Be Obtained By Rotation with our built-in code editor and test cases.
Practice on FleetCode