Matrix Similarity After Cyclic Shifts — Easy Problem & Solution

Problem statement

Each second, every even-indexed row of mat shifts cyclically one place to the left and every odd-indexed row shifts one place to the right. This happens k times.

Return whether the matrix ends up identical to how it started.

Example 1

Input: mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2
Output: true
Explanation: Every row has period 2, so two shifts restore it.

Example 2

Input: mat = [[2,2],[2,2]], k = 3
Output: true
Explanation: Constant rows never change.

Example 3

Input: mat = [[1,2]], k = 1
Output: false

Constraints

• 1 <= mat.length, mat[i].length <= 25
• 1 <= mat[i][j] <= 25
• 1 <= k <= 50
• All rows have the same length.

How to solve Matrix Similarity After Cyclic Shifts

Shifting k times is one shift by k modulo the row length, so nothing needs simulating. The matrix is unchanged exactly when every cell already equals the value that would land on it.

Approach

1. For an even row, the value arriving at column j comes from (j + k) % n.
2. For an odd row, it comes from ((j - k) % n + n) % n.
3. Return false at the first mismatch, true otherwise.

Why it works

Cyclic shifts compose, so k single shifts equal one shift by k mod n — which is why the modulo appears and why k up to 50 costs nothing. The + n before the second modulo fixes languages where % on a negative operand returns a negative result.

Complexity

• Time — O(m · n)
• Space — O(1)

Pitfalls

• Simulating k shifts row by row is unnecessary work and easy to get subtly wrong.
• (j - k) % n is negative in most languages — normalise it.
• Even and odd rows shift in opposite directions.

Reference solution

Python

from typing import List

def areSimilar(mat: List[List[int]], k: int) -> bool:
    n = len(mat[0])
    for i, row in enumerate(mat):
        for j in range(n):
            src = (j + k) % n if i % 2 == 0 else (j - k) % n
            if row[j] != row[src]:
                return False
    return True

JavaScript

var areSimilar = function(mat, k) {
    var n = mat[0].length;
    for (var i = 0; i < mat.length; i++) {
        for (var j = 0; j < n; j++) {
            var src = i % 2 === 0 ? (j + k) % n : (((j - k) % n) + n) % n;
            if (mat[i][j] !== mat[i][src]) return false;
        }
    }
    return true;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy