Opening the reading…
Opening the reading…
MATRIX › MATRIX TRANSFORMATION AND MODIFICATION
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Try it yourself first →A cyclic shift only changes where each value appears inside its row. After n shifts, every value has completed a full cycle and is back at its starting column, so only k modulo n matters. Once k is reduced, you do not need to build any intermediate matrix or repeat the operation k times.
For an even row shifted left, the value that ends at column j originally came from column (j + k) modulo n. For an odd row shifted right, it came from column (j - k) modulo n. Compare that expected source value with the current value at column j. If every comparison matches, the shifted matrix is identical to the original.
| MEASURE | BOUND | WHY |
|---|---|---|
| Time | O(mn) | The nested loops inspect at most one source value for each of the mn matrix positions, and each comparison uses constant-time indexing. Early exit can make a particular run faster, but the worst case checks every cell. |
| Space | O(1) extra | The solution stores only m, n, k, target, and loop variables; it creates no shifted matrix and uses no container proportional to the input. The boolean output needs no storage to count, and the bound stays O(1) for every matrix shape. |
#include <vector>
using namespace std;
class Solution {
public:
bool areSimilar(vector<vector<int>>& mat, int k) {
int m = mat.size();
int n = mat[0].size();
k %= n;
if (k == 0) return true;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int target;
if (i % 2 == 0) {
target = mat[i][(j + k) % n];
} else {
target = mat[i][(j - k + n) % n];
}
if (mat[i][j] != target) return false;
}
}
return true;
}
};The comparison is written from the destination's point of view. mat[i][j] is the value currently at destination column j, while target is the value that the shifted row would place there. The early return after k %= n is safe because a zero shift leaves every row unchanged, so no cell comparison can add information.