Matrix Similarity After Cyclic Shifts
Source: leetcode
Difficulty: Easy
Tags: array, math, matrix, simulation

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.leetcode.com/uploads/2024/05/19/lshift.jpg)


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


![](https://assets.leetcode.com/uploads/2024/05/19/rshift-stlone.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.leetcode.com/uploads/2024/05/19/t1-2.jpg)



**Example 2:**



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


**Output:** true


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/05/19/t1-3.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`




C++ solution:
class Solution {
public:
    bool areSimilar(vector<vector<int>>& mat, int k) {
        int n = mat.size(), m = mat[0].size();
        k %= m;
        for (int i = 0; i < n; i++) {
            int shift = i % 2 == 0 ? k : -k;
            for (int j = 0; j < m; j++) {
                if (mat[i][j] != mat[i][(j+shift+m) % m]) return false;
            }
        }
        return true;
    }
};

Go solution:
func areSimilar(mat [][]int, k int) bool {
    n := len(mat[0])
    k = k % n
    idx := k

    for i, row := range(mat) {
        if i % 2 == 1 {
            idx = n - k
        } else {
            idx = k
        }
        for j := 0; j < n; j++ {
            if row[j] != row[idx % n] {
                return false
            }
            idx += 1
        }
    }

    return true
}

Java solution:
class Solution {
    public boolean areSimilar(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(mat[i][j] != mat[i][(j+k) % n])
                    return false;
            }
        }
        return true;
    }
}

JavaScript solution:
/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {boolean}
 */
var areSimilar = function(mat, k) {
    const n = mat.length;
    const l = mat[0].length;
    k = k % l;

    for (let i=0; i<n; i++) {
       const el1 = [...mat[i].slice(k), ...mat[i].slice(0, k)].join('');
       const el2 = mat[i].join('');

       if (el1 !== el2) return false
    }

    return true
};

Python solution:
class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        nrows, ncols = len(mat), len(mat[0])

        k %= ncols

        if k == 0:
            return True

        for i, row in enumerate(mat):
            if i % 2 == 0:
                r = row[k:] + row[:k]
                if r != row:
                    return False
            else:
                r = row[-k:] + row[:-k]
                if r != row:
                    return False
        
        return True

Ruby solution:
# @param {Integer[][]} mat
# @param {Integer} k
# @return {Boolean}
def are_similar(mat, k)
    @row_size = mat[0].size
    @max_x = mat[0].size - 1
    if k > @row_size
        k = k % @row_size
    end

    # Traverse mat and gets updated position for each element.
    # If the value of the new position doesnt match the current element value
    # return false.
    mat.each_with_index do |row, y|
        row.each_with_index do |col_val, x|
            new_x = updated_position x, k
            if mat[y][new_x] != col_val
                return false
            end
        end
    end

    true
end

# Calculates new x position based on k.
def updated_position x, k
    new_x = x
    if x.even?
        new_x = x + k
    else
        new_x = x - k
    end

    if new_x > (@max_x)
        new_x = new_x % @row_size
    elsif new_x < 0
        new_x = new_x + @row_size
    end

    new_x
end