Matrix Similarity After Cyclic Shifts
EasyPrompt
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 <= 251 <= mat[i].length <= 251 <= mat[i][j] <= 251 <= 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, calledcurrentMat. - Get the number of columns,
n. - Loop
ktimes. In each iteration, representing one step of the shift:- Create a new
m x nmatrix callednextMat. - Iterate through each row
iand columnjofcurrentMat. - If
iis an even index, perform a single left shift:nextMat[i][j] = currentMat[i][(j + 1) % n]. - If
iis an odd index, perform a single right shift:nextMat[i][j] = currentMat[i][(j - 1 + n) % n]. - After filling
nextMat, updatecurrentMatto benextMat.
- Create a new
- After the
kiterations are complete, compare the finalcurrentMatwith the originalmatelement by element. - If all elements match, return
true. Otherwise, returnfalse.
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.
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.
Algorithm
- Get the matrix dimensions
mandn. - Calculate the effective shift amount
s = k % n. This is because shiftingntimes brings a row back to its original state. - Create a new
m x nmatrix,shiftedMat. - Iterate through each row
ifrom0tom-1.- If
iis even, perform a left shift byspositions: for each columnj, setshiftedMat[i][j] = mat[i][(j + s) % n]. - If
iis odd, perform a right shift byspositions: for each columnj, setshiftedMat[i][j] = mat[i][(j - s + n) % n].
- If
- After constructing
shiftedMat, compare it with the originalmatelement by element. - Return
trueif they are identical,falseotherwise.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Get matrix dimensions
mandn. - Calculate the effective shift amount
s = k % n. - If
s == 0, the matrix remains unchanged, so returntrue. - Loop through each row
ifrom0tom-1.- Loop through each column
jfrom0ton-1.- If
iis even (left shift): The element at(j + s) % nmoves toj. For the matrix to be unchanged,mat[i][j]must equalmat[i][(j + s) % n]. If not, returnfalse. - If
iis odd (right shift): The element at(j - s + n) % nmoves toj. For the matrix to be unchanged,mat[i][j]must equalmat[i][(j - s + n) % n]. If not, returnfalse.
- If
- Loop through each column
- If the loops complete without returning
false, it means the condition holds for all cells, so returntrue.
Walkthrough
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 bys), the element that moves into positionjcomes from the original position(j + s) % n. For the matrix to be unchanged,mat[i][j]must be equal tomat[i][(j + s) % n]. - For an odd row
i(right shift bys), the element that moves into positionjcomes from the original position(j - s + n) % n. For the matrix to be unchanged,mat[i][j]must be equal tomat[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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 TrueVideo 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.