Determine Whether Matrix Can Be Obtained By Rotation

Easy
296.

Determine Whether Matrix Can Be Obtained By Rotation

Determine Whether Matrix Can Be Obtained By Rotation is an easy coding problem on arrays and matrix, asked in Amazon and Adobe interviews.

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 <= 8
  • mat[i].length == mat.length
  • mat and target have the same size.
  • Entries are 0 or 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @param {number[][]} target
 * @return {boolean}
 */
var findRotation = function(mat, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 8
  • mat[i].length == mat.length
  • mat and target have the same size.
  • Entries are 0 or 1.

Hints for Determine Whether Matrix Can Be Obtained By Rotation

  1. Hint 1

    There are only four distinct rotations, so try them all.

  2. 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).

  3. 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

  1. For four iterations: if cur == target, return true.
  2. Rotate: new[r][c] = cur[n-1-c][r].
  3. 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 False

Java

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