Matrix Similarity After Cyclic Shifts - Video Solutions

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.