Matrix Similarity After Cyclic Shifts

Difficulty: Easy | Acceptance: 74.30% | Paid: No Topics: Array, Math, Matrix, Simulation

You are given a 0-indexed m x n integer matrix mat and an integer k. You have to apply exactly k cyclic shifts to the matrix.

A cyclic shift is defined as:

• For each row i:
  • If i is even, shift the row to the right by 1 (move the last element to the first position).
  • If i is odd, shift the row to the left by 1 (move the first element to the last position).

Return true if the final matrix is identical to the original matrix, and false otherwise.

• Examples
• Constraints
• Direct Indexing
• Simulation with Modulo

Examples

Example 1

Input: mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2
Output: true
Explanation:
- Row 0 (even): [1,2,1,2] -> shift right 2 -> [1,2,1,2]
- Row 1 (odd):  [5,5,5,5] -> shift left 2 -> [5,5,5,5]
- Row 2 (even): [6,3,6,3] -> shift right 2 -> [6,3,6,3]
The matrix remains identical.

Example 2

Input: mat = [[2,2],[2,2]], k = 3
Output: true
Explanation:
Since all elements are the same, any shift results in the same matrix.

Example 3

Input: mat = [[1,2]], k = 1
Output: false
Explanation:
Row 0 (even): [1,2] -> shift right 1 -> [2,1]. This is not equal to [1,2].

Constraints

m == mat.length
n == mat[i].length
1 <= m, n <= 50
1 <= k <= 10⁹
1 <= mat[i][j] <= 10⁵

Direct Indexing

Intuition Shifting a row of length n by n positions brings it back to the original state. Therefore, applying k shifts is equivalent to applying k % n shifts. We can simply check if the element at each index j matches the element at the index it would move to after k % n shifts.

Steps

• Calculate shift = k % n. If shift is 0, the matrix is identical.
• Iterate through each cell (i, j) in the matrix.
• For even rows i, the element at j moves to (j + shift) % n. Check if mat[i][j] == mat[i][(j + shift) % n].
• For odd rows i, the element at j moves to (j - shift) % n. Check if mat[i][j] == mat[i][(j - shift + n) % n].
• If any check fails, return false. Otherwise, return true.

class Solution:
    def areSimilar(self, mat: list[list[int]], k: int) -> bool:
        m, n = len(mat), len(mat[0])
        k %= n
        if k == 0:
            return True
        
        for i in range(m):
            for j in range(n):
                if i % 2 == 0:
                    # Even row: shift right
                    if mat[i][j] != mat[i][(j + k) % n]:
                        return False
                else:
                    # Odd row: shift left
                    if mat[i][j] != mat[i][(j - k) % n]:
                        return False
        return True

Complexity

• Time: O(m * n)
• Space: O(1)
• Notes: Most efficient approach, avoids unnecessary data manipulation.

Simulation with Modulo

Intuition Since shifting n times returns the row to its original state, we only need to simulate k % n shifts. We can perform the shifts iteratively on the matrix (or a copy) and compare with the original.

Steps

• Calculate shifts = k % n.
• Create a copy of the matrix (or work on the original if allowed, but copying is safer for comparison).
• Loop shifts times:
  • For each row i:
    • If i is even, rotate the row right by 1.
    • If i is odd, rotate the row left by 1.
• After the loop, compare the modified matrix with the original.

from collections import deque

class Solution:
    def areSimilar(self, mat: list[list[int]], k: int) -> bool:
        m, n = len(mat), len(mat[0])
        k %= n
        if k == 0:
            return True

        # Convert rows to deques for efficient rotation
        rows = [deque(row) for row in mat]
        
        for _ in range(k):
            for i in range(m):
                if i % 2 == 0:
                    # Shift right
                    rows[i].rotate(1)
                else:
                    # Shift left
                    rows[i].rotate(-1)
        
        # Compare with original
        for i in range(m):
            if list(rows[i]) != mat[i]:
                return False
        return True

Complexity

• Time: O((k % n) * m * n)
• Space: O(m * n) for the copy (or O(1) if modifying in-place and restoring, though comparison requires original state).
• Notes: Intuitive but less efficient than direct indexing. Since k % n < n <= 50, this is effectively O(m * n²), which is acceptable for given constraints.