Leetcode 2946: Matrix Similarity After Cyclic Shifts

Input: You are given a 2D matrix 'mat' and an integer 'k', where 'mat[i][j]' represents the element in the ith row and jth column.

Example: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 4

Constraints:

• 1 <= mat.length <= 25

• 1 <= mat[i].length <= 25

• 1 <= mat[i][j] <= 25

• 1 <= k <= 50

Output: Return true if the matrix is identical to its original after k shifts, otherwise return false.

Example: For mat = [[1,2,3],[4,5,6],[7,8,9]] and k = 4, the output is false.

Constraints:

Goal: The goal is to determine whether, after k cyclic shifts on the matrix, the matrix will match its original configuration.

Steps:

• For each row in the matrix, determine whether performing cyclic shifts k times results in the same row.

• For even-indexed rows, perform a left cyclic shift; for odd-indexed rows, perform a right cyclic shift.

Goal: The matrix can have up to 25 rows and 25 columns, and k can be at most 50.

Steps:

• mat.length <= 25

• mat[i].length <= 25

• mat[i][j] <= 25

• k <= 50

Assumptions:

• Matrix rows can have different lengths but will be bounded by the constraints.

• Cyclic shifts are defined as moving elements in a row from one end to the other, wrapping around.

• Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 4

• Explanation: After performing 4 shifts, the matrix is no longer identical to the original one, so the result is false.

• Input: mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2

• Explanation: After performing 2 shifts, the matrix becomes identical to its original form, so the result is true.

Approach: To solve the problem, we perform k cyclic shifts on the matrix and compare the result with the original matrix.

Observations:

• Cyclic shifts can be easily simulated for each row by shifting elements accordingly.

• After applying the shifts, comparing the modified matrix with the original will give the desired result.

• We need to ensure that the shifting operation is applied to each row correctly, alternating between left and right shifts for even and odd rows, respectively.

Steps:

• For each row in the matrix, apply the appropriate cyclic shift (left for even rows, right for odd rows).

• After applying all shifts, compare the modified matrix with the original matrix to determine if they are identical.

Empty Inputs:

• The input matrix will always have at least one element, so there will be no empty matrices.

Large Inputs:

• Even though the matrix size can be large (up to 25x25), the complexity of the problem remains manageable due to the constraints.

Special Values:

• If all elements in the matrix are the same, any cyclic shifts will not alter the matrix.

Constraints:

• The constraints ensure that the size of the matrix is small enough to perform the cyclic shifts efficiently.

bool areSimilar(vector<vector<int>>& mat, int k) {
    for (const auto& l : mat) {
        int n = l.size();
        for (int i = 0; i < n; ++i) {
            if (l[i] != l[(i + k) % n]) {
                return false;
            }
        }
    }
    return true;
}

1 : Function Definition

bool areSimilar(vector<vector<int>>& mat, int k) {

Defines the function 'areSimilar' which checks if a 2D matrix can be rotated by 'k' positions to match its original configuration in every row.

2 : Outer Loop

    for (const auto& l : mat) {

Starts iterating through each row 'l' of the matrix 'mat'. The variable 'l' represents a row in the matrix.

3 : Row Size

        int n = l.size();

Calculates the number of elements in the current row 'l' by storing the size of the row in the variable 'n'.

4 : Inner Loop

        for (int i = 0; i < n; ++i) {

Starts an inner loop to iterate over each element 'i' in the current row 'l'.

5 : Rotation Check

            if (l[i] != l[(i + k) % n]) {

Checks if the current element 'l[i]' matches the element at the rotated position '(i + k) % n'. The modulo ensures the index wraps around when it exceeds the size of the row.

6 : Return False

                return false;

If the elements do not match after the rotation, it returns 'false' immediately, indicating the rows are not similar after rotation.

7 : Return True

    return true;

If all rows pass the rotation check, it returns 'true', indicating that the matrix can be rotated to match itself for all rows.

Best Case: O(k * m * n)

Average Case: O(k * m * n)

Worst Case: O(k * m * n)

Description: The time complexity is O(k * m * n) because for each row, we perform a shift k times, and we need to compare each element in the matrix.

Best Case: O(m * n)

Worst Case: O(m * n)

Description: The space complexity is O(m * n) due to the storage needed for the matrix.

Leetcode 2946: Matrix Similarity After Cyclic Shifts

Explore →