#2946

Easy

LeetCode Problem Workspace

Matrix Similarity After Cyclic Shifts

Determine if a matrix returns to its original state after performing cyclic row shifts k times using array and math patterns.

array math matrix simulation

Problem Statement

You are given an m x n integer matrix mat and an integer k. Each row of the matrix is indexed from 0. For every step, rows with even indices are shifted left by one, and rows with odd indices are shifted right by one.

This process is repeated k times. Return true if the matrix after k steps matches the original matrix exactly, otherwise return false.

Examples

Example 1

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

Output: false

In each step left shift is applied to rows 0 and 2 (even indices), and right shift to row 1 (odd index).

Example 2

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

Output: true

Example 3

Input: mat = [[2,2],[2,2]], k = 3

Output: true

As all the values are equal in the matrix, even after performing cyclic shifts the matrix will remain the same.

Constraints

1 <= mat.length <= 25
1 <= mat[i].length <= 25
1 <= mat[i][j] <= 25
1 <= k <= 50

Solution Approach

Reduce Shifts Using Modulo

Since each row cycles back after n shifts, compute effective shifts as k % n. This reduces unnecessary computation and directly connects to the array plus math pattern.

Simulate Row Shifts

Apply left shifts to even rows and right shifts to odd rows for the effective number of shifts. Keep track of each row independently to verify similarity with the original matrix.

Compare with Original Matrix

After applying the effective cyclic shifts, check each row against the corresponding original row. Return true if all rows match, false otherwise.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m * n) for m rows and n columns, as each row may be shifted up to n positions. Space complexity is O(m * n) if a copy of the matrix is used for comparison, or O(1) if shifts are done in place.

What Interviewers Usually Probe

Candidate should identify that k can be reduced modulo n to simplify computation.
Look for understanding of row-wise shift direction based on index parity.
Expect efficient comparison with original matrix rather than simulating all k shifts explicitly.

Common Pitfalls or Variants

Common pitfalls

Forgetting to reduce k modulo the row length leads to unnecessary repeated shifts.
Shifting the wrong direction for even or odd rows will produce incorrect results.
Assuming uniform rows are trivial without verifying the shift direction logic.

Follow-up variants

Matrix similarity after cyclic column shifts instead of row shifts.
Allowing variable shift directions for each row, specified in an input array.
Checking similarity for submatrices after cyclic row shifts rather than the entire matrix.

FAQ

What is the key insight for Matrix Similarity After Cyclic Shifts?

The main insight is that after n shifts a row returns to its original state, so only k % n shifts need to be simulated.

How do I handle even and odd row shifts?

Even-indexed rows are shifted left, odd-indexed rows are shifted right, and this pattern repeats for k steps.

Can I optimize space for this problem?

Yes, you can perform in-place shifts and compare rows to avoid extra memory allocation for the matrix copy.

Does the problem require simulating all k steps?

No, only the effective shifts k % n are necessary because the matrix repeats every n shifts.

What array plus math techniques are used here?

The techniques involve modular arithmetic to reduce shifts and array manipulation to simulate left and right cyclic shifts efficiently.

terminal

Solution

Solution 1: Simulation

We iterate over each element of the matrix and check whether its position after the cyclic shift is the same as the element at the original position.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        n = len(mat[0])
        for i, row in enumerate(mat):
            for j, x in enumerate(row):
                if i % 2 == 1 and x != mat[i][(j + k) % n]:
                    return False
                if i % 2 == 0 and x != mat[i][(j - k + n) % n]:
                    return False
        return True

Continue Practicing

#2961 double modular exponentiation #2965 find missing and repeated values #3044 most frequent prime