# Matrix Similarity After Cyclic Shifts
**Difficulty:** EASY
[External](https://leetcode.com/problems/matrix-similarity-after-cyclic-shifts)
Canonical: https://scaleengineer.com/dsa/problems/matrix-similarity-after-cyclic-shifts
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, Matrix
---
## Problem
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.

![](https://assets.glich.co/dsa/matrix-similarity-after-cyclic-shifts/image0.jpg)

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

![](https://assets.glich.co/dsa/matrix-similarity-after-cyclic-shifts/image1.jpg)

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).

![](https://assets.glich.co/dsa/matrix-similarity-after-cyclic-shifts/image2.jpg)

**Example 2:**

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

**Output:** true

**Explanation:**

![](https://assets.glich.co/dsa/matrix-similarity-after-cyclic-shifts/image3.jpg)

**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
## Brute-Force Simulation
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Optimized Simulation with a Single Shift
This approach improves upon the brute-force simulation by recognizing that `k` individual shifts are equivalent to a single shift of `k` positions. Since the shifts are cyclic, we only need to consider the effective shift amount, which is `k` modulo the number of columns `n`.
**Time:** O(m * n). We iterate through the matrix once to build the shifted matrix and once to compare, resulting in a linear time complexity with respect to the matrix size. · **Space:** O(m * n). We use an extra matrix `shiftedMat` to store the result of the shifts.
**Pros:** Much more efficient than the brute-force simulation, with time complexity independent of `k`.; Still relatively easy to understand.
**Cons:** Requires extra space proportional to the size of the matrix to store the shifted version.
### Explanation
Instead of simulating one shift at a time for `k` times, we can calculate the total shift amount and apply it once. A cyclic shift of a row of length `n` by `k` positions is the same as a shift by `k % n` positions. Let `s = k % n`. We create a new matrix, `shiftedMat`, to store the result of applying this total shift. We iterate through each row of the original matrix. For even rows, we perform a single left cyclic shift by `s` positions. For odd rows, we perform a single right cyclic shift by `s` positions. After constructing the `shiftedMat`, we compare it element-wise with the original `mat`. If they are identical, we return `true`; otherwise, `false`.

```java
class Solution {
    public boolean areSimilar(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        int effectiveShifts = k % n;

        int[][] shiftedMat = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i % 2 == 0) { // Even row: left shift
                    shiftedMat[i][j] = mat[i][(j + effectiveShifts) % n];
                } else { // Odd row: right shift
                    shiftedMat[i][j] = mat[i][(j - effectiveShifts + n) % n];
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] != shiftedMat[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Get the matrix dimensions `m` and `n`.
- Calculate the effective shift amount `s = k % n`. This is because shifting `n` times brings a row back to its original state.
- Create a new `m x n` matrix, `shiftedMat`.
- Iterate through each row `i` from `0` to `m-1`.
  - If `i` is even, perform a left shift by `s` positions: for each column `j`, set `shiftedMat[i][j] = mat[i][(j + s) % n]`.
  - If `i` is odd, perform a right shift by `s` positions: for each column `j`, set `shiftedMat[i][j] = mat[i][(j - s + n) % n]`.
- After constructing `shiftedMat`, compare it with the original `mat` element by element.
- Return `true` if they are identical, `false` otherwise.

## Mathematical Check without Simulation
The most efficient approach avoids any simulation or creation of new matrices. It uses a mathematical insight: for the final matrix to be identical to the original, every element must be equal to the element that will take its place after the shifts. We can directly check this condition for each element without actually performing the shift.
**Time:** O(m * n). We iterate through the matrix exactly once to check the condition for each cell. · **Space:** O(1). We only use a few variables to store dimensions and the effective shift amount, requiring constant extra space.
**Pros:** Most efficient in both time and space.; Avoids creating any auxiliary data structures, leading to O(1) space complexity.; Time complexity is optimal as it requires a single pass through the matrix.
**Cons:** The logic might be slightly less intuitive at first glance compared to direct simulation.
### Explanation
The core idea is to determine for each cell `(i, j)` if its value is identical to the value of the element that will move into its position after `k` shifts. If this holds true for all cells, the matrix is similar to its original state.

First, we calculate the effective number of shifts, `s = k % n`. If `s` is 0, no effective shift occurs, so the matrix is unchanged, and we can return `true`.

We then iterate through each cell `(i, j)` of the matrix.
- For an **even row `i`** (left shift by `s`), the element that moves into position `j` comes from the original position `(j + s) % n`. For the matrix to be unchanged, `mat[i][j]` must be equal to `mat[i][(j + s) % n]`.
- For an **odd row `i`** (right shift by `s`), the element that moves into position `j` comes from the original position `(j - s + n) % n`. For the matrix to be unchanged, `mat[i][j]` must be equal to `mat[i][(j - s + n) % n]`.

If we find any cell where this condition is not met, we can immediately return `false`. If the loops complete without finding any mismatch, we return `true`.

```java
class Solution {
    public boolean areSimilar(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        int effectiveShifts = k % n;

        if (effectiveShifts == 0) {
            return true;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i % 2 == 0) { // Even row: left shift
                    if (mat[i][j] != mat[i][(j + effectiveShifts) % n]) {
                        return false;
                    }
                } else { // Odd row: right shift
                    if (mat[i][j] != mat[i][(j - effectiveShifts + n) % n]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Get matrix dimensions `m` and `n`.
- Calculate the effective shift amount `s = k % n`.
- If `s == 0`, the matrix remains unchanged, so return `true`.
- Loop through each row `i` from `0` to `m-1`.
  - Loop through each column `j` from `0` to `n-1`.
    - If `i` is even (left shift): The element at `(j + s) % n` moves to `j`. For the matrix to be unchanged, `mat[i][j]` must equal `mat[i][(j + s) % n]`. If not, return `false`.
    - If `i` is odd (right shift): The element at `(j - s + n) % n` moves to `j`. For the matrix to be unchanged, `mat[i][j]` must equal `mat[i][(j - s + n) % n]`. If not, return `false`.
- If the loops complete without returning `false`, it means the condition holds for all cells, so return `true`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool areSimilar(vector<vector<int>> &mat, int k) {
    int m = mat.size(), n = mat[0].size();
    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;
  }
};

```

### Python

```python
class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool: n = len(mat[0]) for i, row in enumerate(mat): for j, x in enumerate(row): if i % 2 == 1 and x != mat[i][(j + k) % n]: return False if i % 2 == 0 and x != mat[i][(j - k + n) % n]: return False return True

```