Skip to content

2946. Matrix Similarity After Cyclic Shifts

Description

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

Solutions

Solution 1: Simulation

We iterate over each element of the matrix and check whether its position after the cyclic shift is the same as the element at the original position.

For odd-indexed rows, we shift elements to the right by \(k\) positions, so element \((i, j)\) moves to position \((i, (j + k) \bmod n)\) after the cyclic shift, where \(n\) is the number of columns.

For even-indexed rows, we shift elements to the left by \(k\) positions, so element \((i, j)\) moves to position \((i, (j - k + n) \bmod n)\) after the cyclic shift.

If at any point during the traversal we find that an element's position after the cyclic shift differs from the original, we return \(\text{false}\). If all elements remain the same after the full traversal, we return \(\text{true}\).

The time complexity is \(O(m \times n)\), where \(m\) and \(n\) are the number of rows and columns of the matrix, respectively. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func areSimilar(mat [][]int, k int) bool {
    n := len(mat[0])
    k %= n
    for i, row := range mat {
        for j, x := range row {
            if i%2 == 1 && x != mat[i][(j+k)%n] {
                return false
            }
            if i%2 == 0 && x != mat[i][(j-k+n)%n] {
                return false
            }
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function areSimilar(mat: number[][], k: number): boolean {
    const m = mat.length;
    const n = mat[0].length;
    k %= n;
    for (let i = 0; i < m; ++i) {
        for (let 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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
impl Solution {
    pub fn are_similar(mat: Vec<Vec<i32>>, k: i32) -> bool {
        let m = mat.len();
        let n = mat[0].len();
        let k = (k as usize) % n;

        for i in 0..m {
            for j in 0..n {
                if i % 2 == 1 && mat[i][j] != mat[i][(j + k) % n] {
                    return false;
                }
                if i % 2 == 0 && mat[i][j] != mat[i][(j + n - k) % n] {
                    return false;
                }
            }
        }
        true
    }
}

Comments