Matrix Similarity After Cyclic Shifts

Easy
899.

Matrix Similarity After Cyclic Shifts

Matrix Similarity After Cyclic Shifts is an easy coding problem on arrays, matrix and simulation, asked in Amazon, Adobe and Cognizant interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {boolean}
 */
var areSimilar = function(mat, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Matrix Similarity After Cyclic Shifts — Problem & Solution

Matrix Similarity After Cyclic Shifts solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Matrix Similarity After Cyclic Shifts is an easy coding problem on arrays, matrix and simulation, asked in Amazon, Adobe and Cognizant interviews.

  • Difficulty: Easy
  • Topics: Arrays, Matrix, Simulation
  • Asked at: Amazon, Adobe, Cognizant
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Matrix Similarity After Cyclic Shifts

  1. Hint 1

    Do not actually perform k shifts — compare each cell against where its value would come from.

  2. Hint 2

    After k left shifts, position j holds what used to be at (j + k) % n.

  3. Hint 3

    A right shift is the same with k negated, normalised into range.

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

Java

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

C++

bool areSimilar(vector<vector<int>>& mat, int k) {
    int n = (int) mat[0].size();
    for (int i = 0; i < (int) mat.size(); i++) {
        for (int j = 0; j < n; j++) {
            int src = i % 2 == 0 ? (j + k) % n : (((j - k) % n) + n) % n;
            if (mat[i][j] != mat[i][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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal