Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A cyclic shift changes which original column supplies each position, but it does not require constructing a new row. The matrix remains unchanged exactly when every destination cell equals the source cell selected by its row's shift direction.

Approach

Reduce k modulo the number of columns, since a full row-length shift changes nothing. For every cell at column j, compare it with column (j + k) mod m on even-indexed rows, which shift left. On odd-indexed rows, compare with (j - k) mod m, wrapping negative indices into the valid range, for the right shift.

Return false as soon as a comparison fails. If all comparisons succeed, every shifted row matches its original row, so return true. A reduced shift of zero naturally succeeds without any special reconstruction.

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

        for i in range(n):
            for j in range(m):
                if i % 2 == 0:
                    if mat[i][j] != mat[i][(j + k) % m]:
                        return False
                else:
                    if mat[i][j] != mat[i][(j - k) % m]:
                        return False

        return True

Complexity analysis

Let r and c be the matrix dimensions. Time: O(r * c). Auxiliary space: O(1).