Problem Statement in English

You’re given a matrix mat of size M x N and an integer k. You must perform the following operation on the matrix:

  • For every even-indexed row (0-indexed), you must cyclically shift the elements to the right by k positions.

  • For every odd-indexed row (0-indexed), you must cyclically shift the elements to the left by k positions.

Return true if the matrix is similar to itself after performing the above operation, and false otherwise.

Approach

We just need to simulate the process of cyclically shifting the rows and then compare the resulting matrix with the original matrix.

Remember to use the modulo operator to handle cases where k is greater than N, the number of columns in the matrix.

And we’re done!

Solution in Python


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

        shifts = k % N
        temp = [[0 for _ in range(N)] for _ in range(M)]

        for i in range(M):
            even = i % 2 == 0

            for j in range(N):
                if even:
                    temp[i][(j - shifts) % N] = mat[i][j]
                else:
                    temp[i][(j + shifts) % N] = mat[i][j]

        return temp == mat

Complexity

  • Time: $O(M \times N)$
    Since we iterate through the matrix once to create the shifted matrix and then compare the two matrices.

  • Space: $O(M \times N)$
    Since we’re storing the shifted matrix.

And we are done.