Determine Whether Matrix Can Be Obtained By Rotation solution and explanation
Google
9 more videos on this problem
Determine Whether Matrix Can Be Obtained By Rotation | Simple Detailed | Leetcode 1886 | MIKcodestorywithMIK · 20:15 · 6K views
1886 Determine Whether Matrix Can Be Obtained By Rotation | Zero to FAANG | Solution | LeetcodeProgrammers Zone · 21:36 · 6K views
Leetcode 1886 | Determine Whether Matrix Can Be Obtained By RotationSandip Jana · 7:09 · 4K views
1886. Determine Whether Matrix Can Be Obtained By Rotation (Leetcode Easy)Programming Live with Larry · 7:51 · 1K views
1886 Determine Whether Matrix Can Be Obtained By Rotation |leetcode 1886 | #leetcode 1886 | LeetcodeCoderNight · 6:45 · 682 views
1886. Determine Whether Matrix Can Be Obtained By Rotation | Leetcode Daily - PythonLeetcode Daily · 6:53 · 458 views
Determine Whether Matrix Can Be Obtained By Rotation | Leetcode 1886 | JavaDev Prasad · 10:52 · 453 views
Daily Leetcode #2182: Mar 22, 2026 - 1886. Determine Whether Matrix Can Be Obtained By RotationProgramming Live with Larry · 4:00 · 340 views
Determine Whether Matrix Can Be Obtained By Rotation (LeetCode problem 1886)MCCOMP · 2:23 · 334 views
Determine Whether Matrix Can Be Obtained By Rotation | Leetcode 1886 | Java | Hindi | Daily LeetcodeKernel Queen 👑 · 7:33 · 282 views
The problem
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.
def are_matrices_equal(mat1, mat2):
return mat1 == mat2
def rotate90(mat):
return [list(reversed(col)) for col in zip(*mat)]
class Solution:
def findRotation(self, mat, target):
for _ in range(4):
if are_matrices_equal(mat, target):
return True
mat = rotate90(mat)
return Falseclass Solution {
private boolean areMatricesEqual(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;
}
private void rotate90(int[][] mat) {
int n = mat.length;
for (int i = 0; i < n / 2; i++) {
for (int j = i; j < n - i - 1; j++) {
int temp = mat[i][j];
mat[i][j] = mat[n - j - 1][i];
mat[n - j - 1][i] = mat[n - i - 1][n - j - 1];
mat[n - i - 1][n - j - 1] = mat[j][n - i - 1];
mat[j][n - i - 1] = temp;
}
}
}
public boolean findRotation(int[][] mat, int[][] target) {
for (int i = 0; i < 4; i++) {
if (areMatricesEqual(mat, target)) {
return true;
}
rotate90(mat);
}
return false;
}
}#include <vector>
using namespace std;
bool areMatricesEqual(vector<vector<int>>& mat1, vector<vector<int>>& mat2) {
return mat1 == mat2;
}
void rotate90(vector<vector<int>>& mat) {
int n = mat.size();
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
swap(mat[i][j], mat[j][i]);
}
}
for (int i = 0; i < n; ++i) {
reverse(mat[i].begin(), mat[i].end());
}
}
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
for (int i = 0; i < 4; ++i) {
if (areMatricesEqual(mat, target)) {
return true;
}
rotate90(mat);
}
return false;
}function areMatricesEqual(mat1, mat2) {
for (let i = 0; i < mat1.length; i++) {
for (let j = 0; j < mat1.length; j++) {
if (mat1[i][j] !== mat2[i][j]) return false;
}
}
return true;
}
function rotate90(mat) {
const n = mat.length;
const rotated = mat.map((_, i) => mat.map(row => row[i]).reverse());
return rotated;
}
function findRotation(mat, target) {
for (let i = 0; i < 4; i++) {
if (areMatricesEqual(mat, target)) return true;
mat = rotate90(mat);
}
return false;
}#include <stdbool.h>
#include <string.h>
bool areMatricesEqual(int **mat1, int **mat2, int n) {
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;
}
void rotate90(int **mat, int n) {
for (int i = 0; i < n / 2; i++) {
for (int j = i; j < n - i - 1; j++) {
int temp = mat[i][j];
mat[i][j] = mat[n - j - 1][i];
mat[n - j - 1][i] = mat[n - i - 1][n - j - 1];
mat[n - i - 1][n - j - 1] = mat[j][n - i - 1];
mat[j][n - i - 1] = temp;
}
}
}
bool findRotation(int **mat, int **target, int n) {
for (int k = 0; k < 4; k++) {
if (areMatricesEqual(mat, target, n))
return true;
rotate90(mat, n);
}
return false;
}public class Solution {
private bool AreMatricesEqual(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;
}
private void Rotate90(int[][] mat) {
int n = mat.Length;
for (int i = 0; i < n / 2; i++) {
for (int j = i; j < n - i - 1; j++) {
int temp = mat[i][j];
mat[i][j] = mat[n - j - 1][i];
mat[n - j - 1][i] = mat[n - i - 1][n - j - 1];
mat[n - i - 1][n - j - 1] = mat[j][n - i - 1];
mat[j][n - i - 1] = temp;
}
}
}
public bool FindRotation(int[][] mat, int[][] target) {
for (int i = 0; i < 4; i++) {
if (AreMatricesEqual(mat, target)) {
return true;
}
Rotate90(mat);
}
return false;
}
}In this Python solution, the matrix rotation is achieved using list comprehension and zip to rotate the matrix. We check the equality of the current matrix to the target and perform this check after each rotation.
Time Complexity: O(n^2)
Space Complexity: O(n^2), creating a new matrix for the rotated version.
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.
def rotate(mat):
n = len(mat)
return [list(reversed(col)) for col in zip(*mat)]
class Solution:
def findRotation(self, mat, target):
for _ in range(4):
if mat == target:
return True
mat = rotate(mat)
return Falseclass Solution {
private void rotate90(int[][] mat) {
int n = mat.length;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = temp;
}
}
for (int i = 0; i < n; i++) {
int lo = 0, hi = n - 1;
while (lo < hi) {
int tmp = mat[i][lo];
mat[i][lo] = mat[i][hi];
mat[i][hi] = tmp;
lo++; hi--;
}
}
}
public boolean findRotation(int[][] mat, int[][] target) {
int[][][] rotations = new int[4][mat.length][mat[0].length];
for (int i = 0; i < 4; i++) {
if (i > 0) rotate90(mat);
rotations[i] = Arrays.stream(mat).map(int[]::clone).toArray(int[][]::new);
}
for (int[][] rot : rotations) {
if (Arrays.deepEquals(rot, target)) {
return true;
}
}
return false;
}
}#include <vector>
#include <algorithm>
using namespace std;
void rotate(vector<vector<int>>& mat) {
int n = mat.size();
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
swap(mat[i][j], mat[j][i]);
}
}
for (int i = 0; i < n; ++i) {
reverse(mat[i].begin(), mat[i].end());
}
}
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
vector<vector<vector<int>>> rotations(4, mat);
for (int i = 1; i < 4; ++i) {
rotate(rotations[i]);
}
for (const auto& rot : rotations) {
if (rot == target) {
return true;
}
}
return false;
}function rotate(mat) {
const n = mat.length;
const rotated = mat.map((_, i) => mat.map(row => row[i]).reverse());
return rotated;
}
function findRotation(mat, target) {
for (let i = 0; i < 4; i++) {
if (JSON.stringify(mat) === JSON.stringify(target)) return true;
mat = rotate(mat);
}
return false;
}#include <stdbool.h>
#include <string.h>
void transpose(int **mat, int n) {
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
int tmp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = tmp;
}
}
}
void reverseColumns(int **mat, int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0, k = n - 1; j < k; ++j, --k) {
int tmp = mat[j][i];
mat[j][i] = mat[k][i];
mat[k][i] = tmp;
}
}
}
void generateRotations(int **mat, int n, int ***rotations) {
// Store initial
rotations[0] = mat;
for (int k = 1; k < 4; ++k) {
transpose(rotations[k - 1], n);
reverseColumns(rotations[k - 1], n);
rotations[k] = rotations[k - 1];
}
}
bool findRotation(int **mat, int **target, int n) {
int *rotations[4];
generateRotations(mat, n, rotations);
for (int i = 0; i < 4; ++i) {
if (memcmp(rotations[i], target, n * n * sizeof(int)) == 0) {
return true;
}
}
return false;
}public class Solution {
private void Rotate90(int[][] mat) {
int n = mat.Length;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = temp;
}
}
for (int i = 0; i < n; i++) {
Array.Reverse(mat[i]);
}
}
public bool FindRotation(int[][] mat, int[][] target) {
for (int i = 0; i < 4; i++) {
if (i > 0) Rotate90(mat);
if (AreMatricesEqual(mat, target)) {
return true;
}
}
return false;
}
private bool AreMatricesEqual(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;
}
}In this Python solution, the matrix is rotated by transposing it and reversing columns. It then checks all precomputed rotations against the target matrix.
Time Complexity: O(n^2)
Space Complexity: O(n^2), as new list is created for each rotation.
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).
function findRotation(mat: number[][], target: number[][]): boolean {
const n = mat.length;
let ok = 0b1111;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (mat[i][j] !== target[i][j]) {
ok &= ~0b0001;
}
if (mat[j][n - 1 - i] !== target[i][j]) {
ok &= ~0b0010;
}
if (mat[n - 1 - i][n - 1 - j] !== target[i][j]) {
ok &= ~0b0100;
}
if (mat[n - 1 - j][i] !== target[i][j]) {
ok &= ~0b1000;
}
if (ok === 0) {
return false;
}
}
}
return ok !== 0;
}func findRotation(mat [][]int, target [][]int) bool {
n := len(mat)
ok := 0b1111
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if mat[i][j] != target[i][j] {
ok &= ^0b0001
}
if mat[j][n-1-i] != target[i][j] {
ok &= ^0b0010
}
if mat[n-1-i][n-1-j] != target[i][j] {
ok &= ^0b0100
}
if mat[n-1-j][i] != target[i][j] {
ok &= ^0b1000
}
if ok == 0 {
return false
}
}
}
return ok != 0
}class Solution {
fun findRotation(mat: Array<IntArray>, target: Array<IntArray>): Boolean {
val n = mat.size
var ok = 0b1111
for (i in 0 until n) {
for (j in 0 until n) {
if (mat[i][j] != target[i][j]) {
ok = ok and 0b1110
}
if (mat[j][n - 1 - i] != target[i][j]) {
ok = ok and 0b1101
}
if (mat[n - 1 - i][n - 1 - j] != target[i][j]) {
ok = ok and 0b1011
}
if (mat[n - 1 - j][i] != target[i][j]) {
ok = ok and 0b0111
}
if (ok == 0) {
return false
}
}
}
return ok != 0
}
}impl Solution {
pub fn find_rotation(mat: Vec<Vec<i32>>, target: Vec<Vec<i32>>) -> bool {
let n = mat.len();
let mut ok: i32 = 0b1111;
for i in 0..n {
for j in 0..n {
if mat[i][j] != target[i][j] {
ok &= !0b0001;
}
if mat[j][n - 1 - i] != target[i][j] {
ok &= !0b0010;
}
if mat[n - 1 - i][n - 1 - j] != target[i][j] {
ok &= !0b0100;
}
if mat[n - 1 - j][i] != target[i][j] {
ok &= !0b1000;
}
if ok == 0 {
return false;
}
}
}
ok != 0
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Rotate and Compare | Time Complexity: O(n^2) Space Complexity: O(n^2), creating a new matrix for the rotated version. |
| Precompute 4 Rotations | Time Complexity: O(n^2) Space Complexity: O(n^2), as new list is created for each rotation. |
| In-Place Comparison | – |
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. |
Frequently asked questions
Is Determine Whether Matrix Can Be Obtained By Rotation easy or hard?
Determine Whether Matrix Can Be Obtained By Rotation is classified as an Easy problem on LeetCode. The challenge mainly involves understanding how indices change during a matrix rotation and implementing the comparison correctly.
Determine Whether Matrix Can Be Obtained By Rotation Python/Java solution
A typical Python or Java solution rotates the matrix in 90-degree increments and compares it with the target matrix after each step. The logic uses nested loops to remap indices and runs in O(n^2) time with either constant or O(n^2) extra space depending on implementation.
How to solve Determine Whether Matrix Can Be Obtained By Rotation in O(n^2)?
Perform up to four rotations of the matrix and compare with the target after each rotation. A 90° rotation maps position (i, j) to (j, n-1-i). Each rotation and comparison takes O(n^2), and since there are only four possible rotations, the overall complexity remains O(n^2).
What is the best approach for Determine Whether Matrix Can Be Obtained By Rotation?
The rotate-and-compare method is the most practical approach. Rotate the matrix by 90 degrees up to four times and compare it with the target matrix after each rotation. Each comparison scans all cells, giving an overall time complexity of O(n^2) and constant extra space.
Is Determine Whether Matrix Can Be Obtained By Rotation asked at Google/Amazon/Meta?
Matrix manipulation and rotation problems frequently appear in interviews at companies like Amazon, Google, and Meta. This problem tests understanding of index mapping in 2D arrays and careful iteration through matrix coordinates.
What data structure is used in Determine Whether Matrix Can Be Obtained By Rotation?
The problem primarily uses a 2D array (matrix). The solution relies on index transformations within the matrix to simulate 90°, 180°, and 270° rotations while iterating through elements for comparison.
What is the time complexity of Determine Whether Matrix Can Be Obtained By Rotation?
The time complexity is O(n^2). Each matrix comparison requires scanning all n x n elements, and there are at most four possible rotations. Since 4 is a constant, the complexity simplifies to O(n^2).