algoadvance

Leetcode 1886. Determine Whether Matrix Can Be Obtained By Rotation

Problem Statement

You are given two n x n binary matrices mat and target. You can rotate mat by 90 degrees (clockwise) any number of times. Return true if it is possible to make mat equal to target by rotating mat in 90-degree increments; otherwise, return false.

Example:

Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
Output: true
Explanation: We can rotate mat 90 degrees to get target.

Constraints:

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

Clarifying Questions

To fully understand the problem, we may want to ask:

• Are there any restrictions on the number of rotations (e.g., count should be minimized)?
• Are both matrices guaranteed to have the same dimensions and contain only binary values (0 and 1)?

Strategy

1. Define Rotation Operation: Create a function to rotate the matrix 90 degrees clockwise.
2. Check All Possible Rotations: Rotate the input matrix mat up to three times and check after each rotation whether it matches the target matrix.
3. Return Result: If any rotation results in mat being equal to target, return true. If none do, return false.

Code

Here is the C++ code to solve the problem:

#include <vector>

using namespace std;

// Function to rotate the given matrix 90 degrees clockwise
vector<vector<int>> rotate90Clockwise(vector<vector<int>>& mat) {
    int n = mat.size();
    vector<vector<int>> rotatedMat(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            rotatedMat[j][n - 1 - i] = mat[i][j];
        }
    }
    return rotatedMat;
}

// Function to check if mat can be rotated to match target
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
    for (int i = 0; i < 4; ++i) {
        if (mat == target) {
            return true;
        }
        mat = rotate90Clockwise(mat);
    }
    return false;
}

Time Complexity

• Rotation Complexity: Each 90-degree rotation operation has a time complexity of O(n^2), where n is the dimension of the matrix.
• Comparison Complexity: Each comparison of the mat with target is also O(n^2).
• Total Complexity: We perform up to four rotations and at most four comparisons. Therefore, the total time complexity is O(4 * n^2) which simplifies to O(n^2).

This solution is efficient given the problem constraints and ensures that we check all possible rotations in a systematic way.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?