Determine Whether Matrix Can Be Obtained By Rotation Solution
Determine Whether Matrix Can Be Obtained By Rotation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Determine Whether Matrix Can Be Obtained By Rotation is an easy coding problem on arrays and matrix, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Matrix
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two n × n binary matrices mat and target, return true if mat can be made equal to target by rotating it 90 degrees clockwise any number of times (including zero).
Example 1
Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
Output: true
Explanation: One rotation suffices.
Example 2
Input: mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
Output: false
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
Constraints
1 <= mat.length <= 8mat[i].length == mat.lengthmat and target have the same size.Entries are 0 or 1.
Hints for Determine Whether Matrix Can Be Obtained By Rotation
Hint 1
There are only four distinct rotations, so try them all.
Hint 2
A 90-degree clockwise rotation maps
(r, c)to(c, n - 1 - r); equivalently the new(r, c)reads the old(n - 1 - c, r).Hint 3
Compare after each rotation, including before the first one.
How to solve Determine Whether Matrix Can Be Obtained By Rotation
Only four rotations exist; compare, rotate 90° clockwise, and repeat up to four times.
Approach
- For four iterations: if
cur == target, returntrue. - Rotate:
new[r][c] = cur[n-1-c][r]. - Return
false.
Why it works
Rotating four times returns to the start, so checking before each of four rotations covers every distinct orientation.
Complexity
- Time —
O(n²) - Space —
O(n²)
Pitfalls
- Compare before the first rotation so the zero-rotation case is included.
Reference solution
Python
def findRotation(mat, target) -> bool:
cur = [row[:] for row in mat]
n = len(mat)
for _ in range(4):
if cur == target:
return True
cur = [[cur[n - 1 - c][r] for c in range(n)] for r in range(n)]
return FalseJava
public static boolean findRotation(int[][] mat, int[][] target) {
int n = mat.length;
int[][] cur = new int[n][n];
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) cur[r][c] = mat[r][c];
}
for (int k = 0; k < 4; k++) {
boolean same = true;
for (int r = 0; r < n && same; r++) {
for (int c = 0; c < n; c++) {
if (cur[r][c] != target[r][c]) { same = false; break; }
}
}
if (same) return true;
int[][] next = new int[n][n];
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) next[r][c] = cur[n - 1 - c][r];
}
cur = next;
}
return false;
}C++
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
int n = (int) mat.size();
vector<vector<int>> cur = mat;
for (int k = 0; k < 4; k++) {
if (cur == target) return true;
vector<vector<int>> next(n, vector<int>(n, 0));
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) next[r][c] = cur[n - 1 - c][r];
}
cur = next;
}
return false;
}JavaScript
var findRotation = function(mat, target) {
const n = mat.length;
let cur = [];
for (let r = 0; r < n; r++) cur.push(mat[r].slice());
const same = function(a, b) {
for (let r = 0; r < n; r++) {
for (let c = 0; c < n; c++) {
if (a[r][c] !== b[r][c]) return false;
}
}
return true;
};
for (let k = 0; k < 4; k++) {
if (same(cur, target)) return true;
const next = [];
for (let r = 0; r < n; r++) {
const row = [];
for (let c = 0; c < n; c++) row.push(cur[n - 1 - c][r]);
next.push(row);
}
cur = next;
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal