Watch 10 video solutions for Matrix Similarity After Cyclic Shifts, a easy level problem involving Array, Math, Matrix. This walkthrough by codestorywithMIK has 5,115 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 <= 50Problem Overview: You are given an m x n matrix and an integer k. Each row undergoes a cyclic shift: even-indexed rows shift left by k, and odd-indexed rows shift right by k. The task is to determine whether the matrix remains exactly the same after applying these shifts.
The key observation is that cyclic shifts simply remap column indices. Instead of physically shifting elements, you can compute where each element would land after the operation and compare it with the original value.
Approach 1: Cycle Detection Using Modulo (O(m*n) time, O(n) space)
This approach simulates the cyclic shift for each row. For every row, create a temporary array and place each element at its shifted index using modulo arithmetic. For even rows, compute the new index as (j - k % n + n) % n to represent a left shift. For odd rows, compute (j + k) % n to represent a right shift. After constructing the shifted row, compare it with the original row to check if they match exactly.
This method closely mirrors the actual operation described in the problem, which makes it easy to reason about. However, it requires additional space for the temporary row. The time complexity is O(m*n) because every element is processed once, and the space complexity is O(n) for the temporary storage.
Approach 2: Direct Comparison Using Index Mapping (O(m*n) time, O(1) space)
Instead of constructing the shifted row, directly check whether each element would remain the same after the cyclic shift. For each position (i, j), compute the column index from which the element would originate after the shift. If i is even, compare matrix[i][j] with matrix[i][(j + k) % n]. If i is odd, compare with matrix[i][(j - k % n + n) % n]. If any comparison fails, the matrix cannot remain unchanged.
This removes the need for a temporary array and performs the check in a single pass. The algorithm still runs in O(m*n) time but uses O(1) extra space. The technique relies on simple index arithmetic and fits well with problems involving cyclic structures in array and matrix manipulation.
Recommended for interviews: The direct comparison approach is typically expected. It demonstrates that you understand cyclic shifts and can translate them into index mapping without extra memory. Implementing the simulation first can help clarify the idea, but the optimized version shows stronger problem-solving skills in simulation-style problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Cycle Detection Using Modulo (Simulation) | O(m*n) | O(n) | When you want a straightforward simulation of the shift operation |
| Direct Comparison Using Index Mapping | O(m*n) | O(1) | Preferred in interviews; avoids extra memory by comparing shifted indices directly |