Matrix Similarity After Cyclic Shifts - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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 1: Cycle Detection Using Modulo
The main insight is that a row returns to its original state after `len` shifts for a row of length `len`. Therefore, instead of performing `k` shifts, we only need to perform `k % len` shifts for each row. This is a key observation because it reduces the computational work drastically.
By applying modulo operation, we only perform the effective shifts necessary and then manually compare the matrix post-transformation with its original state.
The function takes the matrix `mat` and integer `k` as inputs. For each row, it calculates the effective number of shifts needed (using modulo operation) and accordingly performs the cyclic shift operation. After shifting, it directly compares the shifted rows with the original rows to determine if the matrix remains unchanged.
Complexity
Time Complexity: O(m * n) because each element in the matrix is potentially shifted once.
Space Complexity: O(n) for storing the temporarily shifted row.
Approach 2: Temporal Complexity Reduction Using Direct Comparison
In this approach, instead of creating and comparing entire rows during each transformation, we focus on analyzing the positions of individual elements directly. By calculating whether each element will return to its original position after `k` transformations, based on their row's parity (even or odd), we can assert the final result.
This solution focuses on direct comparison by iterating over each element position and calculating where it should be after `k` shifts using modulo arithmetic. If at any index the value doesn't match, it concludes non-identity immediately.
Complexity
Time Complexity: O(m * n), where m is number of rows and n is number of columns.
Space Complexity: O(1) because no extra space is needed besides constant space for variables.
Approach 3: 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 false. If all elements remain the same after the full traversal, we return 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).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Cycle Detection Using Modulo | Time Complexity: O(m * n) because each element in the matrix is potentially shifted once. |
| Temporal Complexity Reduction Using Direct Comparison | Time Complexity: O(m * n), where m is number of rows and n is number of columns. |
| Simulation | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Matrix Similarity After Cyclic Shifts | 2 Simple Approaches | Leetcode 2946 | codestorywithMIK • codestorywithMIK • 5,389 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Matrix Similarity After Cyclic Shifts easy or hard?
How to solve Matrix Similarity After Cyclic Shifts in O(m*n)?
What is the best approach for Matrix Similarity After Cyclic Shifts?
What data structure is used in Matrix Similarity After Cyclic Shifts?
What is the time complexity of Matrix Similarity After Cyclic Shifts?
Matrix Similarity After Cyclic Shifts Python or Java solution approach?
Is Matrix Similarity After Cyclic Shifts asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Matrix Similarity After Cyclic Shifts with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor