1886. Determine Whether Matrix Can Be Obtained By Rotation

EasyArrayMatrix

Problem Description

The problem provides two n x n binary matrices: mat and target. A binary matrix is a matrix where each element is either 0 or 1. The goal is to determine whether it is possible to make the matrix mat identical to the matrix target by rotating mat in 90-degree increments. The task is to check all possible rotations of mat and see if any rotation matches the target. If at least one rotation results in mat being the same as target, the function should return true. Otherwise, if none of the rotations yield the target matrix, the function should return false. Note that it is possible to rotate mat up to three times to achieve this since a fourth rotation would bring the matrix back to its original orientation.

Intuition

To solve this problem, we need to simulate the rotation of the matrix and compare the result with the target matrix after each rotation. A 90-degree rotation of a matrix can be achieved by reversing the matrix along its horizontal axis (i.e., flipping it upside down) and then taking the transpose. The transpose of a matrix is obtained by switching the rows with the columns, which means element [i][j] becomes [j][i].

The intuition behind the solution is to apply this transformation to mat up to four times (since rotating four times would return the matrix to its original state), each time checking if the resulting matrix is equal to target. In Python, this rotation can be conveniently performed using a combination of list comprehensions and the zip function, which groups the elements of the rows (after reversing mat) into columns, effectively transposing them.

The steps for a 90-degree rotation are:

Flip the matrix upside down (mat[::-1])
Transpose the matrix (achieved by zip(*mat) after the flip)
Convert the zipped elements back into lists ([list(col) for col in zipped])
Compare with target (if mat == target)

The function findRotation continuously applies this rotation method up to four times or until mat matches target. If a match is found before the fourth rotation, it returns true. If no match is found after all possible rotations, it returns false.

Solution Approach

The solution approach can be explained as follows:

Create a Rotation Function: The solution defines an inline function within the loop that performs a 90-degree clockwise rotation on mat. This is done by flipping the matrix vertically first (mat[::-1]) and then transposing it, which in Python can be effortlessly implemented with the zip function. The zip(*mat[::-1]) statement pairs row elements with column indices, effectively rotating the matrix.
Loop Through Rotations: It initiates a loop that will run four times, each iteration representing a 90-degree rotation. The loop is used because four rotations will bring the matrix back to its initial position. Hence, beyond this, additional rotations would only repeat previous states.
Transform and Compare: Inside the loop, the matrix mat is rotated using the rotation function from step 1. After each rotation, mat is compared to target (if mat == target). If at any point the matrices match, the function immediately returns true because we have found a valid rotation that turns mat into target.
Handling Non-Matching Cases: If the loop completes without finding a matching rotation (i.e., all four rotations do not result in a matrix equal to target), the function returns false. This implies that there is no sequence of 90-degree rotations that can transform mat into target.

The solution elegantly leverages Python's advanced list comprehension and the zip function to perform matrix rotations cleanly and concisely. The decision to check for equality only four times is based on the mathematical fact that any square matrix will return to its original orientation after four 90-degree rotations. The process is highly efficient, avoiding unnecessary calculations or rotations.

This solution has a time complexity of O(n^2) for each rotation due to the matrix traversal, where n is the number of rows/columns in the matrix. Since a fixed number of rotations (at most 4) are performed, the overall time complexity remains O(n^2). The space complexity is O(n^2) as well, which arises from the storage needed for the rotated matrix at each step.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following 3x3 matrices mat and target:

mat:

1 2 3
4 5 6
7 8 9

target:

7 4 1
8 5 2
9 6 3

First Rotation (0-degree, the original mat):

We compare mat with target. Clearly, they are not identical, so we proceed to rotate mat.

Second Rotation (90-degree clockwise rotation):

Flip mat upside down:

7 8 9
4 5 6
1 2 3

Transpose the flipped matrix:

7 4 1
8 5 2
9 6 3

After rotation, we compare the matrix with target. Now, mat and target are identical.

Since mat matches target after the second rotation, the function would return true at this point, indicating that it is possible to make the matrix mat identical to target by rotating mat in 90-degree increments.

If mat had not matched target, we would have continued to the third and fourth rotations to check all possibilities before determining that mat cannot be matched with target through rotations.

Solution Implementation

1class Solution:
2    def findRotation(self, matrix, target):
3        # Try each of the four rotations
4        for _ in range(4):
5            # Rotate the matrix by 90 degrees clockwise
6            matrix = [list(row) for row in zip(*matrix[::-1])]
7          
8            # Check if the rotated matrix matches the target matrix
9            if matrix == target:
10                # If a match is found, return True
11                return True
12        # If none of the rotations match the target, return False
13        return False
14

1class Solution {
2
3    // Checks if the matrix "mat" can be rotated to match the matrix "target".
4    public boolean findRotation(int[][] mat, int[][] target) {
5        // Determine the size of the matrix
6        int n = mat.length;
7
8        // Try rotating the matrix 0, 90, 180, and 270 degrees
9        for (int k = 0; k < 4; ++k) {
10            // Rotate the matrix by 90 degrees
11            int[][] rotated = new int[n][n];
12            for (int i = 0; i < n; ++i) {
13                for (int j = 0; j < n; ++j) {
14                    // When rotating 90 degrees, the new row is the old column,
15                    // and the new column is n - 1 minus the old row.
16                    rotated[i][j] = mat[j][n - i - 1];
17                }
18            }
19
20            // Check if the rotated matrix matches the target matrix
21            if (areMatricesEqual(rotated, target)) {
22                return true;
23            }
24
25            // Update mat to be the rotated matrix for the next comparison
26            mat = rotated;
27        }
28
29        // If none of the rotations match, return false
30        return false;
31    }
32
33    // Helper method to check if two matrices are equal
34    private boolean areMatricesEqual(int[][] a, int[][] b) {
35        int n = a.length;
36
37        // Compare each element of the matrices
38        for (int i = 0; i < n; ++i) {
39            for (int j = 0; j < n; ++j) {
40                if (a[i][j] != b[i][j]) {
41                    // If any element does not match, the matrices are not equal
42                    return false;
43                }
44            }
45        }
46
47        // All elements match, the matrices are equal
48        return true;
49    }
50}
51

1class Solution {
2public:
3    // This function checks if the matrix 'mat' can be rotated to match the 'target' matrix.
4    bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
5        int size = mat.size(); // 'size' holds the dimension of the matrix.
6        // We will attempt to rotate the matrix up to 4 times (0, 90, 180, 270 degrees).
7        for (int rotation = 0; rotation < 4; ++rotation) {
8            vector<vector<int>> rotatedMatrix(size, vector<int>(size));
9            // Rotate the matrix by 90 degrees clockwise.
10            for (int i = 0; i < size; ++i) {
11                for (int j = 0; j < size; ++j) {
12                    rotatedMatrix[i][j] = mat[j][size - i - 1];
13                }
14            }
15            // After the rotation, check if the rotatedMatrix matches the target.
16            if (rotatedMatrix == target) {
17                return true; // If match found, return true.
18            }
19            // Update 'mat' to be the newly rotated matrix for the next iteration.
20            mat = rotatedMatrix;
21        }
22        // If no matching rotation found, return false.
23        return false;
24    }
25};
26

1// Function to check if a matrix can be rotated to match a target matrix.
2function findRotation(mat: number[][], target: number[][]): boolean {
3    // Try four rotations.
4    for (let k = 0; k < 4; k++) {
5        rotate(mat); // Rotate the matrix.
6        if (isEqual(mat, target)) {
7            // If the matrix after rotation equals the target matrix, return true.
8            return true;
9        }
10    }
11    // If none of the rotations match the target, return false.
12    return false;
13}
14
15// Function to check if two matrices are equal.
16function isEqual(matrixA: number[][], matrixB: number[][]): boolean {
17    const size = matrixA.length;
18    for (let i = 0; i < size; i++) {
19        for (let j = 0; j < size; j++) {
20            // If any corresponding elements differ, return false.
21            if (matrixA[i][j] !== matrixB[i][j]) {
22                return false;
23            }
24        }
25    }
26    // If all elements are equivalent, the matrices are equal.
27    return true;
28}
29
30// Function to rotate a matrix 90 degrees clockwise.
31function rotate(matrix: number[][]): void {
32    const size = matrix.length;
33    // Only iterate over the first half of rows and first half of columns for a square matrix.
34    for (let i = 0; i < size >> 1; i++) {
35        for (let j = 0; j < (size + 1) >> 1; j++) {
36            // Perform a four-way swap of elements in clockwise direction.
37            [
38                matrix[i][j],
39                matrix[size - 1 - j][i],
40                matrix[size - 1 - i][size - 1 - j],
41                matrix[j][size - 1 - i],
42            ] = [
43                matrix[size - 1 - j][i],
44                matrix[size - 1 - i][size - 1 - j],
45                matrix[j][size - 1 - i],
46                matrix[i][j],
47            ];
48        }
49    }
50}
51

Time and Space Complexity

The given Python function findRotation checks whether one matrix is a rotation of another. It does this by rotating mat up to four times (0 degrees, 90 degrees, 180 degrees, and 270 degrees rotations) and comparing it to target after each rotation.

The time complexity of the function is determined by these major factors:

The number of rotations - which is constant, at 4.
The cost of each rotation - which includes reversing the rows of mat (O(n)) and then zipping and list conversion (O(n^2)).
The comparison of mat and target - which is O(n^2) where n is the dimension size of the matrix mat.

So for each rotation, the total time cost is O(n) + O(n^2) = O(n^2), since zip(*mat[::-1]) essentially involves looking at all n^2 elements of the matrix. And since we rotate up to 4 times, the total time complexity is 4 * O(n^2), which simplifies to O(n^2).

The space complexity is determined by the extra space needed to store the rotated matrix:

The reversed matrix mat[::-1] does not use extra space as it is a shallow copy that references the same rows of mat.
However, [list(col) for col in zip(*mat[::-1])] creates a new list of lists for each rotation. This list of lists contains n lists of n integers, so it uses O(n^2) space.

Therefore, the space complexity of the function is O(n^2) as it needs space to store a copy of the matrix each time it is rotated.

In summary:

Time complexity: O(n^2)
Space complexity: O(n^2)

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don’t know