algoadvance

Leetcode 1886. Determine Whether Matrix Can Be Obtained By Rotation

Problem Statement

Leetcode Problem 1886: Determine Whether Matrix Can Be Obtained By Rotation

Given two n x n binary matrices mat and target, return true if it is possible to obtain target by rotating mat in 90-degree increments, otherwise return false.

Clarifying Questions

  1. Matrix Size: What is the maximum and minimum size for the matrices?
    • The problem guarantees that both matrices are n x n. Typically, n can range from 1 to 10.
  2. Binary Values: Are the matrices strictly binary (0s and 1s)?
    • Yes, the matrices consist solely of binary values.
  3. Rotation Increments: Should the rotations be exactly 90 degrees each time?
    • Yes, the rotations are specifically in 90-degree increments.

Strategy

  1. Rotation Function: Create a helper function to rotate the matrix 90 degrees clockwise.
  2. Comparison: After each rotation (0, 90, 180, 270 degrees), compare the rotated matrix to the target matrix.
  3. Efficiency: We need to ensure our solution is efficient with clear matrix operations and comparisons.

Code

public class Solution {
    public boolean findRotation(int[][] mat, int[][] target) {
        int n = mat.length;
        
        for (int i = 0; i < 4; i++) {  // Checking for 0, 90, 180, and 270 degrees rotations
            if (areMatricesEqual(mat, target)) {
                return true;
            }
            mat = rotate90(mat);
        }
        
        return false;
    }
    
    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 int[][] rotate90(int[][] mat) {
        int n = mat.length;
        int[][] rotated = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rotated[j][n - 1 - i] = mat[i][j];
            }
        }
        
        return rotated;
    }
}

Time Complexity

  1. Rotation Function: Rotating a matrix of size n x n takes O(n^2) time.
  2. Matrix Comparison: Comparing two matrices of size n x n also takes O(n^2) time.
  3. Overall Complexity: Since we might perform 3 rotations and comparisons in the worst case, the overall time complexity is O(3 * n^2) -> O(n^2).

This solution efficiently handles the requirements and constraints given, ensuring correctness while maintaining readability.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI