LeetCode 2946 - Matrix Similarity After Cyclic Shifts

LeetCode Problem 2946

Difficulty: 🟢 Easy
Topics: Array, Math, Matrix, Simulation

Solution

Problem Understanding

This problem asks us to determine whether a matrix remains identical to its original form after applying a specific cyclic shifting operation exactly k times.

We are given an m x n integer matrix mat, where m is the number of rows and n is the number of columns. Each row is processed differently depending on whether its index is even or odd:

• Rows with even indices (0, 2, 4, ...) are cyclically shifted to the left.
• Rows with odd indices (1, 3, 5, ...) are cyclically shifted to the right.

A cyclic shift means elements wrap around instead of disappearing. For example, a left shift of [1,2,3,4] produces [2,3,4,1], while a right shift produces [4,1,2,3].

The process happens exactly k times. After all shifts are complete, we must check whether the resulting matrix is identical to the original matrix. If every row matches its original state, we return true; otherwise, we return false.

An important observation is that cyclic shifts repeat in cycles. Since each row contains n elements, shifting a row by n positions returns it to its original arrangement. This means performing k shifts is equivalent to performing k % n shifts. For example, if a row length is 5, then shifting 7 times is equivalent to shifting 2 times.

The constraints are small:

• 1 <= mat.length <= 25
• 1 <= mat[i].length <= 25
• 1 <= mat[i][j] <= 25
• 1 <= k <= 50

These bounds mean even a simulation-based approach is feasible. However, we can still improve the solution by avoiding unnecessary repeated shifting and instead directly checking where each element should end up after the net shift.

Several edge cases deserve attention:

A matrix with only one column (n = 1) will always remain unchanged because any cyclic shift of a single-element row produces the same row.

If k is a multiple of n, every row returns to its original position regardless of values, so the answer is always true.

Rows containing repeated values can look unchanged even after shifting. For example, [5,5,5,5] remains identical after any number of shifts.

A naive implementation that repeatedly simulates every shift risks unnecessary work and may introduce indexing mistakes, especially when wrapping around the row boundaries.

Approaches

Brute Force Approach

The brute-force solution directly simulates the process exactly as described.

For each of the k operations:

• Shift every even-indexed row left by one position.
• Shift every odd-indexed row right by one position.

After all shifts are complete, compare the resulting matrix with the original matrix.

This approach is correct because it faithfully reproduces the transformation process step by step. However, repeatedly shifting rows introduces unnecessary work. Since a row of length n repeats after n shifts, simulating all k operations can be wasteful.

Even though constraints are small enough that this would pass, it is not the cleanest or most efficient solution.

Optimal Approach

The key insight is that cyclic shifts repeat every n steps, where n is the row length.

Instead of simulating k individual shifts, we only care about the effective shift amount:

$$\text{effectiveShift} = k \bmod n$$

Then, for each row, we directly determine where each element should appear after the shift and compare it with the original row.

For an even-indexed row shifted left:

$$\text{newPosition} = (j + shift) \bmod n$$

For an odd-indexed row shifted right:

$$\text{newPosition} = (j - shift + n) \bmod n$$

Rather than building a new matrix, we compare expected values directly. If any mismatch is found, we immediately return false.

This avoids unnecessary repeated simulation and makes the implementation simpler.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n × k)	O(n)	Simulates every shift step explicitly
Optimal	O(m × n)	O(1)	Uses modular arithmetic to check final positions directly

Algorithm Walkthrough

1. Determine the dimensions of the matrix.

Let m be the number of rows and n be the number of columns. Since cyclic shifting repeats every n operations, we only care about the effective shift amount. 2. Compute the effective shift.

Calculate:

shift = k % n

If shift == 0, every row returns to its original configuration, so we can immediately return true. 3. Process each row independently.

Since rows shift independently, iterate through every row index i. 4. Compare elements based on row parity.

For each column index j, determine which original element should appear at position j after shifting.

If the row index is even, the row shifts left. Therefore, the element expected at column j comes from:

(j + shift) % n

If the row index is odd, the row shifts right. Therefore, the expected source position is:

(j - shift + n) % n

5. Check for mismatches immediately.

Compare the expected value with the actual value in the matrix. If they differ, return false immediately because the matrix cannot match the original. 6. Return true if all checks pass.

If every row and column matches correctly, the matrix remains unchanged after k shifts.

Why it works

The algorithm works because cyclic shifts are periodic. A row of length n returns to its original arrangement after exactly n shifts. Therefore, k % n captures the only meaningful displacement.

For every position in the matrix, we compute exactly which original element should occupy that position after the shifts. Since we verify every cell independently and return false on the first mismatch, the algorithm guarantees correctness. If all cells match, then the final transformed matrix must be identical to the original matrix.

Python Solution

from typing import List

class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        rows = len(mat)
        cols = len(mat[0])

        shift = k % cols

        if shift == 0:
            return True

        for row_index in range(rows):
            for col_index in range(cols):
                if row_index % 2 == 0:
                    expected_col = (col_index + shift) % cols
                else:
                    expected_col = (col_index - shift + cols) % cols

                if mat[row_index][col_index] != mat[row_index][expected_col]:
                    return False

        return True

The implementation begins by determining the matrix dimensions. Since cyclic shifts repeat every cols operations, we compute shift = k % cols to eliminate unnecessary work.

If the effective shift is zero, every row returns to its original arrangement automatically, so we return True.

Next, we iterate through every row and column. Depending on whether the row index is even or odd, we compute the column index where the matching element should come from after shifting.

For even rows, we use a left-shift formula. For odd rows, we use a right-shift formula. Instead of creating a shifted copy of the matrix, we directly compare values in-place.

As soon as a mismatch appears, we return False. If the loops finish without mismatches, the matrix must remain unchanged, so we return True.

Go Solution

func areSimilar(mat [][]int, k int) bool {
	rows := len(mat)
	cols := len(mat[0])

	shift := k % cols

	if shift == 0 {
		return true
	}

	for rowIndex := 0; rowIndex < rows; rowIndex++ {
		for colIndex := 0; colIndex < cols; colIndex++ {
			var expectedCol int

			if rowIndex%2 == 0 {
				expectedCol = (colIndex + shift) % cols
			} else {
				expectedCol = (colIndex - shift + cols) % cols
			}

			if mat[rowIndex][colIndex] != mat[rowIndex][expectedCol] {
				return false
			}
		}
	}

	return true
}

The Go implementation follows the same logic as the Python solution. Since Go slices always track their length explicitly, accessing dimensions is straightforward through len().

Unlike Python, Go does not support negative modulo behavior in the same way, so we explicitly add cols before applying % cols to guarantee a non-negative index:

(colIndex - shift + cols) % cols

No extra memory is allocated because comparisons are performed directly on the original matrix.

Worked Examples

Example 1

Input:

mat = [[1,2,3],
       [4,5,6],
       [7,8,9]]
k = 4

First compute:

n = 3
shift = 4 % 3 = 1

Row	Type	Original Row	Shifted Result
0	Even, left	[1,2,3]	[2,3,1]
1	Odd, right	[4,5,6]	[6,4,5]
2	Even, left	[7,8,9]	[8,9,7]

Compare with original:

Original: [1,2,3]
Shifted : [2,3,1]

Immediately different.

Output:

false

Example 2

Input:

mat = [[1,2,1,2],
       [5,5,5,5],
       [6,3,6,3]]
k = 2

Compute:

n = 4
shift = 2 % 4 = 2

Row	Type	Original Row	Shifted Result
0	Even, left	[1,2,1,2]	[1,2,1,2]
1	Odd, right	[5,5,5,5]	[5,5,5,5]
2	Even, left	[6,3,6,3]	[6,3,6,3]

Every row matches the original.

Output:

true

Example 3

Input:

mat = [[2,2],
       [2,2]]
k = 3

Compute:

n = 2
shift = 3 % 2 = 1

After shifting:

Row	Type	Original Row	Shifted Result
0	Even, left	[2,2]	[2,2]
1	Odd, right	[2,2]	[2,2]

Since all values are identical, the matrix remains unchanged.

Output:

true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every matrix cell is checked once
Space	O(1)	Only a few variables are used

The algorithm visits each element exactly once and performs constant-time arithmetic for each comparison. Since no additional matrix or auxiliary data structure is created, the extra memory usage remains constant.

Test Cases

solution = Solution()

# Provided examples
assert solution.areSimilar([[1,2,3],[4,5,6],[7,8,9]], 4) is False  # example 1
assert solution.areSimilar([[1,2,1,2],[5,5,5,5],[6,3,6,3]], 2) is True  # example 2
assert solution.areSimilar([[2,2],[2,2]], 3) is True  # example 3

# Single row
assert solution.areSimilar([[1,2,3,1,2,3]], 3) is True  # repeating pattern

# Single column
assert solution.areSimilar([[1],[2],[3]], 10) is True  # shifts do nothing

# k multiple of row length
assert solution.areSimilar([[1,2,3],[4,5,6]], 6) is True  # complete cycle

# Non-similar matrix
assert solution.areSimilar([[1,2,3],[4,5,6]], 1) is False  # basic mismatch

# Repeated values remain unchanged
assert solution.areSimilar([[5,5,5],[7,7,7]], 4) is True  # uniform rows

# Alternating pattern survives shift
assert solution.areSimilar([[1,2,1,2]], 2) is True  # periodic pattern

# Minimal input
assert solution.areSimilar([[1]], 1) is True  # smallest matrix

Test	Why
Example 1	Validates non-matching shift
Example 2	Validates repeating pattern restoration
Example 3	Ensures uniform values work correctly
Single row	Confirms even-row logic alone
Single column	Ensures shifting size one behaves correctly
k multiple of row length	Tests modulo optimization
Non-similar matrix	Confirms mismatch detection
Repeated values	Verifies identical-value stability
Alternating pattern	Tests periodic repetition
Minimal input	Confirms smallest constraints work

Edge Cases

Single Column Matrix

When the matrix contains only one column, every cyclic shift becomes meaningless because there is only one possible arrangement. A careless implementation might still attempt index arithmetic and introduce bugs, especially around modulo operations. Our implementation handles this naturally because k % 1 == 0, causing an immediate True return.

k Larger Than Row Length

A naive implementation may unnecessarily simulate all k operations, even though cyclic shifts repeat every n steps. For example, shifting a row of length 4 by 50 positions is equivalent to shifting it by 2 positions. Our solution avoids wasted work using k % cols.

Rows with Repeated Values

Rows such as [5,5,5,5] remain visually unchanged after shifting, even though positions technically move. A buggy implementation might incorrectly assume movement implies a mismatch. Our comparison logic checks values directly after the effective shift, ensuring repeated values are handled correctly.

Periodic Patterns

Rows with repeating sequences such as [1,2,1,2] can return to the same arrangement after fewer than n shifts. A naive implementation that only checks whether positions moved may incorrectly return false. Since our algorithm compares actual resulting values, periodic structures are correctly recognized as unchanged.