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 process 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

Thinking

Odd rows shift right by \(k\) and even rows left by \(k\); the matrix must stay unchanged. \(k\) may be reduced modulo the width, but comparing the cell that would land on \((i,j)\) avoids rotating.

On odd rows inspect \(mat[i][(j+k)\bmod n]\), on even rows \(mat[i][(j-k+n)\bmod n]\). One mismatch rejects. The matrix is at most \(25 \times 25\).

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