Problem Description

You are given a matrix mat of size m x n (m rows and n columns) containing integers, and an integer k. The rows of the matrix are indexed starting from 0.

The problem asks you to perform a specific shifting operation on the matrix k times:

For each operation:

• Even-indexed rows (rows 0, 2, 4, 6, ...) are cyclically shifted to the left by one position

  • In a left cyclic shift, the first element moves to the end, and all other elements move one position to the left
  • For example: [1, 2, 3, 4] becomes [2, 3, 4, 1]

• Odd-indexed rows (rows 1, 3, 5, 7, ...) are cyclically shifted to the right by one position

  • In a right cyclic shift, the last element moves to the beginning, and all other elements move one position to the right
  • For example: [1, 2, 3, 4] becomes [4, 1, 2, 3]

After performing these shifting operations k times, you need to determine if the resulting matrix is identical to the original matrix.

Return true if the matrix returns to its original state after k operations, and false otherwise.

Key insight: The solution leverages the cyclic nature of the shifts. For a row of length n, shifting left or right n times brings the row back to its original state. Therefore, we only need to check if shifting by k % n positions results in the original configuration.

Intuition

The key observation is that cyclic shifts have a periodic nature. If a row has n elements, then shifting it left or right n times will bring it back to its original position. This means we don't actually need to simulate k shifts - we can directly check if the matrix equals itself after k shifts.

Instead of performing the shifts k times and then comparing, we can be clever and check if each element in the original matrix appears in the position it would be after k shifts. This is much more efficient.

For any element at position j in a row:

• After k left shifts, it would be at position (j - k) % n
• After k right shifts, it would be at position (j + k) % n

So the approach is to iterate through each element and verify:

• For even-indexed rows (which shift left): Check if the element at position j equals the element that would end up at position j after k left shifts. This means checking if mat[i][j] equals mat[i][(j - k) % n].

• For odd-indexed rows (which shift right): Check if the element at position j equals the element that would end up at position j after k right shifts. This means checking if mat[i][j] equals mat[i][(j + k) % n].

The modulo operation % n handles the cyclic nature - when indices go beyond the row boundaries, they wrap around. We add n in the left shift formula (j - k + n) % n to handle negative values correctly in the modulo operation.

If all elements match their expected positions after k shifts, the matrix returns to its original state, so we return true. If any element doesn't match, we return false.

Learn more about Math patterns.

Solution Approach

The solution implements a direct verification approach without actually performing the shifts. Here's how the algorithm works:

1. Get the row length: Store n = len(mat[0]) as the number of columns in each row. This is used for the modulo operations.

2. Iterate through each row and element: Use enumerate(mat) to get both the row index i and the row content. Then iterate through each element in the row with its position j and value x.

3. Check based on row parity:

   • For odd-indexed rows (i % 2 == 1): These rows shift right. After k right shifts, the element currently at position j would have come from position (j - k) % n. So we check if x != mat[i][(j + k) % n]. If they don't match, the matrix doesn't return to its original state, so return False.

   • For even-indexed rows (i % 2 == 0): These rows shift left. After k left shifts, the element currently at position j would have come from position (j + k) % n. So we check if x != mat[i][(j - k + n) % n]. The + n is added to handle negative indices correctly with modulo. If they don't match, return False.

4. Return result: If we've checked all elements and found no mismatches, the matrix returns to its original state after k operations, so return True.

The algorithm has:

• Time Complexity: O(m × n) where m is the number of rows and n is the number of columns, as we check each element once.
• Space Complexity: O(1) as we only use a constant amount of extra space for variables.

The beauty of this solution is that it leverages the mathematical property of cyclic shifts to avoid simulating the actual shifting process, making it both elegant and efficient.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Consider the matrix:

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

And k = 3.

Since each row has length n = 3, and we're shifting k = 3 times, we're essentially shifting each row by exactly its length. This should bring the matrix back to its original state (since 3 shifts in a row of 3 elements completes a full cycle).

Step-by-step verification:

Row 0 (even-indexed, shifts left):

• For element at position j=0 with value 1:
  • After 3 left shifts, position 0 should contain what was at position (0 + 3) % 3 = 0
  • Check: mat[0][0] = 1 equals mat[0][0] = 1 ✓
• For element at position j=1 with value 2:
  • After 3 left shifts, position 1 should contain what was at position (1 + 3) % 3 = 1
  • Check: mat[0][1] = 2 equals mat[0][1] = 2 ✓
• For element at position j=2 with value 3:
  • After 3 left shifts, position 2 should contain what was at position (2 + 3) % 3 = 2
  • Check: mat[0][2] = 3 equals mat[0][2] = 3 ✓

Row 1 (odd-indexed, shifts right):

• For element at position j=0 with value 4:
  • After 3 right shifts, position 0 should contain what was at position (0 - 3 + 3) % 3 = 0
  • Check: mat[1][0] = 4 equals mat[1][0] = 4 ✓
• Similar checks for positions 1 and 2 all pass ✓

Row 2 (even-indexed, shifts left):

• Similar to Row 0, all checks pass ✓

Result: Return true since all elements match their expected positions.

Counter-example with k = 1:

Same matrix, but k = 1:

Row 0 (even-indexed, shifts left once):

• Original: [1, 2, 3] → After 1 left shift: [2, 3, 1]
• Checking position j=0:
  • Current value: 1
  • After 1 left shift, position 0 should contain what was at position (0 + 1) % 3 = 1
  • Check: mat[0][0] = 1 should equal mat[0][1] = 2
  • 1 ≠ 2 ✗

Since we found a mismatch, we immediately return false. The matrix does not return to its original state after 1 shift.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the matrix.

The algorithm uses nested loops:

• The outer loop iterates through all m rows of the matrix
• The inner loop iterates through all n elements in each row
• For each element, it performs a constant time operation: checking equality with another element in the same row (accessed via modulo indexing)
• The modulo operation (j + k) % n or (j - k + n) % n takes O(1) time
• Array access mat[i][...] takes O(1) time

Therefore, the total time complexity is O(m * n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variables n, i, j, and x are all primitive types that take O(1) space
• No additional data structures are created
• The enumeration and iteration are done in-place without creating copies of the data

The space complexity is constant, O(1), as it doesn't depend on the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Modulo Calculation for Negative Indices

One of the most common mistakes is incorrectly handling the modulo operation when dealing with left shifts (even-indexed rows). When calculating (col_idx - k) % num_cols, if col_idx - k is negative, the modulo operation in some programming languages (like Python) can produce unexpected results.

Incorrect approach:

# This might seem intuitive but can fail with negative values
shifted_position = (col_idx - k) % num_cols

Why it fails:

• If col_idx = 1, k = 3, and num_cols = 5
• (1 - 3) % 5 = -2 % 5 = -2 in some implementations
• This gives an invalid array index

Correct approach:

# Add num_cols to ensure the result is always positive
shifted_position = (col_idx - k + num_cols) % num_cols

2. Confusing Shift Direction Logic

Another pitfall is mixing up which direction to check for verification. The problem states:

• Even rows shift LEFT
• Odd rows shift RIGHT

But when verifying if the matrix returns to original state, you need to think "where did this element come FROM":

• For left shifts: current element at position j came from position (j + k) % n
• For right shifts: current element at position j came from position (j - k) % n

Incorrect approach:

if row_idx % 2 == 0:  # Even row - shifts left
    # Wrong: checking where element goes TO instead of where it came FROM
    shifted_position = (col_idx - k + num_cols) % num_cols

Correct approach:

if row_idx % 2 == 0:  # Even row - shifts left
    # Correct: checking where element came FROM after k left shifts
    shifted_position = (col_idx + k) % num_cols

3. Not Optimizing k with Modulo

While not affecting correctness, failing to optimize k can lead to unnecessary large calculations:

Suboptimal approach:

# Using k directly without optimization
shifted_position = (col_idx + k) % num_cols

Optimized approach:

# Pre-compute k % num_cols once
k = k % num_cols
shifted_position = (col_idx + k) % num_cols

This optimization is particularly important when k is very large, as it reduces the computation needed for the modulo operations throughout the algorithm.