Determine Whether Matrix Can Be Obtained By Rotation

Determine Whether Matrix Can Be Obtained By Rotation - Problem

Array Matrix Easy

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.

A 90-degree rotation means rotating the matrix clockwise by 90 degrees. You can perform this rotation 0, 1, 2, or 3 times to check if any of the resulting matrices match the target.

Input & Output

Example 1 — Basic Rotation Match

$ Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]]

› Output: true

💡 Note: Rotating mat 90° clockwise gives [[1,0],[0,1]] which equals target. The top-left 0 moves to top-right, top-right 1 moves to bottom-right, etc.

Example 2 — No Rotation Match

$ Input: mat = [[0,1],[1,1]], target = [[1,0],[0,1]]

› Output: false

💡 Note: None of the 4 rotations (0°, 90°, 180°, 270°) of mat equals target. mat has two 1s but target has them in different positions that can't be achieved by rotation.

Example 3 — 180° Rotation Match

$ Input: mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]

› Output: true

💡 Note: Rotating mat 180° gives target. The bottom row [1,1,1] becomes the top row, and the top row [0,0,0] becomes the bottom row.

Constraints

n == mat.length == mat[i].length == target.length == target[i].length
1 ≤ n ≤ 10
mat[i][j] and target[i][j] are either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Matrices

Given mat and target matrices to compare

Try Rotations

Check if any 90° rotation of mat equals target

Match Found

Return true if any rotation matches, false otherwise

Key Takeaway

🎯 Key Insight: Only 4 rotations are possible - check each one efficiently using position mapping formulas.

Asked in

f Facebook 15 G Google 8 Apple 6

The key insight is that there are only 4 possible rotations (0°, 90°, 180°, 270°) to check. The optimal approach calculates rotated positions using mathematical formulas without storing intermediate matrices. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ In-Place Rotation Check	O(n²)	O(1)	Check rotations without storing intermediate matrices by comparing positions directly
Generate All Rotations	O(n²)	O(n²)	Generate all 4 possible rotations and check if any matches target

In-Place Rotation Check — Algorithm Steps

For each rotation (0°, 90°, 180°, 270°)
Calculate rotated positions using mathematical formulas
Compare elements at rotated positions directly
Return true on first match, false if none match

Visualization

Tap to expand

Step-by-Step Walkthrough

Position Mapping

For each rotation, calculate where each element maps to

Direct Comparison

Compare mat[i][j] with target[rotated_i][rotated_j]

Early Return

Return true immediately on first match

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool checkRotation(int** mat, int** target, int rotation, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int r, c;
            // Calculate position after rotation
            if (rotation == 0) {  // 0 degrees
                r = i; c = j;
            } else if (rotation == 1) {  // 90 degrees
                r = j; c = n - 1 - i;
            } else if (rotation == 2) {  // 180 degrees
                r = n - 1 - i; c = n - 1 - j;
            } else {  // 270 degrees
                r = n - 1 - j; c = i;
            }
            
            if (mat[i][j] != target[r][c]) {
                return false;
            }
        }
    }
    return true;
}

bool solution(int** mat, int** target, int n) {
    // Check all 4 possible rotations
    for (int rotation = 0; rotation < 4; rotation++) {
        if (checkRotation(mat, target, rotation, n)) {
            return true;
        }
    }
    
    return false;
}

int main() {
    // For simplicity, assume input is small 2x2 or 3x3 matrix
    int n = 2; // This should be determined from input
    
    int** mat = (int**)malloc(n * sizeof(int*));
    int** target = (int**)malloc(n * sizeof(int*));
    
    for (int i = 0; i < n; i++) {
        mat[i] = (int*)malloc(n * sizeof(int));
        target[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Simple hardcoded parsing for demonstration
    mat[0][0] = 0; mat[0][1] = 1;
    mat[1][0] = 1; mat[1][1] = 0;
    
    target[0][0] = 1; target[0][1] = 0;
    target[1][0] = 0; target[1][1] = 1;
    
    bool result = solution(mat, target, n);
    printf(result ? "true\n" : "false\n");
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(mat[i]);
        free(target[i]);
    }
    free(mat);
    free(target);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

We check up to 4 rotations, each requiring O(n²) comparisons

⚠ Quadratic Growth

Space Complexity

O(1)

No extra space needed, just calculate positions on the fly

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

In-Place Rotation Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler