Scale Engineer

Matrix Similarity After Cyclic Shifts

Easy
#2626Time: O(k * m * n). The outer loop runs `k` times, and inside it, we iterate through the `m x n` matrix to perform the shifts.Space: O(m * n). We use an extra matrix `currentMat` and `nextMat` to store the state of the matrix at each step.
Patterns
Math
Data structures
ArrayMatrix

Prompt

You are given an m x n integer matrix mat and an integer k. The matrix rows are 0-indexed.

The following proccess happens k times:

  • Even-indexed rows (0, 2, 4, ...) are cyclically shifted to the left.

  • Odd-indexed rows (1, 3, 5, ...) are cyclically shifted to the right.

Return true if the final modified matrix after k steps is identical to the original matrix, and false otherwise.

 

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 4

Output: false

Explanation:

In each step left shift is applied to rows 0 and 2 (even indices), and right shift to row 1 (odd index).

Example 2:

Input: mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2

Output: true

Explanation:

Example 3:

Input: mat = [[2,2],[2,2]], k = 3

Output: true

Explanation:

As all the values are equal in the matrix, even after performing cyclic shifts the matrix will remain the same.

 

Constraints:

  • 1 <= mat.length <= 25
  • 1 <= mat[i].length <= 25
  • 1 <= mat[i][j] <= 25
  • 1 <= k <= 50

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. It performs the cyclic shifts one by one for k steps and then compares the final matrix with the original one.

Algorithm

  • Create a copy of the input matrix, mat, called currentMat.
  • Get the number of columns, n.
  • Loop k times. In each iteration, representing one step of the shift:
    • Create a new m x n matrix called nextMat.
    • Iterate through each row i and column j of currentMat.
    • If i is an even index, perform a single left shift: nextMat[i][j] = currentMat[i][(j + 1) % n].
    • If i is an odd index, perform a single right shift: nextMat[i][j] = currentMat[i][(j - 1 + n) % n].
    • After filling nextMat, update currentMat to be nextMat.
  • After the k iterations are complete, compare the final currentMat with the original mat element by element.
  • If all elements match, return true. Otherwise, return false.

Walkthrough

We start by creating a copy of the original matrix to modify, let's call it currentMat. We then loop k times. In each iteration, we simulate one step of the cyclic shift process. For each step, we create a new temporary matrix, nextMat, to store the result of the shift. We iterate through each row of currentMat. If the row index is even, we perform a single left cyclic shift. If the row index is odd, we perform a single right cyclic shift. After processing all rows, we update currentMat with the contents of nextMat. After k iterations, we compare the final currentMat with the original mat. If they are identical, we return true; otherwise, false.

class Solution {    public boolean areSimilar(int[][] mat, int k) {        int m = mat.length;        int n = mat[0].length;        int[][] currentMat = new int[m][n];        for (int i = 0; i < m; i++) {            System.arraycopy(mat[i], 0, currentMat[i], 0, n);        }         for (int step = 0; step < k; step++) {            int[][] nextMat = new int[m][n];            for (int i = 0; i < m; i++) {                if (i % 2 == 0) { // Even row: left shift                    for (int j = 0; j < n; j++) {                        nextMat[i][j] = currentMat[i][(j + 1) % n];                    }                } else { // Odd row: right shift                    for (int j = 0; j < n; j++) {                        nextMat[i][j] = currentMat[i][(j - 1 + n) % n];                    }                }            }            currentMat = nextMat;        }         for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (mat[i][j] != currentMat[i][j]) {                    return false;                }            }        }        return true;    }}

Complexity

Time

O(k * m * n). The outer loop runs `k` times, and inside it, we iterate through the `m x n` matrix to perform the shifts.

Space

O(m * n). We use an extra matrix `currentMat` and `nextMat` to store the state of the matrix at each step.

Trade-offs

Pros

  • Simple to understand and implement as it directly follows the problem description.

Cons

  • Highly inefficient, especially for large values of k.

  • Time complexity is proportional to k, which can lead to Time Limit Exceeded errors.

  • Requires significant extra space to store intermediate matrices.

Solutions

class Solution {public  boolean areSimilar(int[][] mat, int k) {    int m = mat.length, n = mat[0].length;    k %= n;    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        if (i % 2 == 1 && mat[i][j] != mat[i][(j + k) % n]) {          return false;        }        if (i % 2 == 0 && mat[i][j] != mat[i][(j - k + n) % n]) {          return false;        }      }    }    return true;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem