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 <= 50The 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.
C++
Java
C#
JavaScript
C
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.
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.
C++
Java
C#
JavaScript
C
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 | 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. |
Spiral Matrix - Microsoft Interview Question - Leetcode 54 • NeetCode • 191,743 views views
Watch 9 more video solutions →Practice Matrix Similarity After Cyclic Shifts with our built-in code editor and test cases.
Practice on FleetCode