Matrix Similarity After Cyclic Shifts - Practice Coding Problems

Matrix Similarity After Cyclic Shifts - Problem

You are given an m x n integer matrix mat and an integer k. The matrix rows are 0-indexed.

The following process happens k times:

Even-indexed rows (0, 2, 4, ...) are cyclically shifted to the left
Odd-indexed rows (1, 3, 5, ...) are cyclically shifted to the right

Return true if the final modified matrix after k steps is identical to the original matrix, and false otherwise.

Input & Output

Example 1 — Basic 2x2 Matrix

$ Input: mat = [[1,2],[3,4]], k = 2

› Output: true

💡 Note: After 1 shift: row 0 becomes [2,1], row 1 becomes [4,3]. After 2 shifts: row 0 becomes [1,2], row 1 becomes [3,4]. Matrix returns to original.

Example 2 — Single Shift

$ Input: mat = [[2,1],[3,4]], k = 1

› Output: false

💡 Note: After 1 shift: row 0 becomes [1,2], row 1 becomes [4,3]. This is different from original [[2,1],[3,4]].

Example 3 — Large k Value

$ Input: mat = [[1,2,1,2]], k = 4

› Output: true

💡 Note: Row has period 2 (repeats every 2 elements). After k=4 shifts, 4 % 2 = 0, so it returns to original.

Constraints

1 ≤ m, n ≤ 25
1 ≤ mat[i][j] ≤ 99
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Matrix with even/odd rows and shift count k

Process

Even rows shift left, odd rows shift right

Output

Check if matrix returns to original

Key Takeaway

🎯 Key Insight: Use mathematical periods instead of simulation to efficiently determine if matrix returns to original state

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that cyclic shifts follow predictable patterns. Each row returns to its original state after a certain number of shifts (the period). The mathematical approach calculates this period and checks if k is divisible by it, avoiding expensive simulation. Time: O(m × n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Optimization	O(m × n)	O(1)	Use modular arithmetic to calculate effective shifts without simulation
Simulation	O(k × m × n)	O(m × n)	Simulate each shift operation k times and compare with original matrix

Mathematical Optimization — Algorithm Steps

Step 1: For each row, calculate effective shifts as k % row_length
Step 2: If effective shifts is 0, row returns to original
Step 3: Return true only if all rows return to original

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Period

Determine shortest cycle length for each row

Check Modulo

k % period must equal 0 for original state

Result

True if all rows return to original

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int** mat, int m, int n, int k) {
    for (int i = 0; i < m; i++) {
        int* row = mat[i];
        
        // Find the period of this row
        int period = n;
        for (int p = 1; p <= n; p++) {
            if (n % p == 0) {
                bool isPeriod = true;
                for (int j = 0; j < n; j++) {
                    if (row[j] != row[j % p]) {
                        isPeriod = false;
                        break;
                    }
                }
                if (isPeriod) {
                    period = p;
                    break;
                }
            }
        }
        
        // Check if k shifts return row to original
        if (k % period != 0) {
            return false;
        }
    }
    
    return true;
}

int main() {
    // Simple parsing for small test cases
    int m = 2, n = 2;
    int** mat = malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        mat[i] = malloc(n * sizeof(int));
    }
    
    // Read matrix values (simplified)
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse [[1,2],[3,4]] format (simplified)
    mat[0][0] = 1; mat[0][1] = 2;
    mat[1][0] = 3; mat[1][1] = 4;
    
    int k;
    scanf("%d", &k);
    
    bool result = solution(mat, m, n, k);
    printf(result ? "true\n" : "false\n");
    
    for (int i = 0; i < m; i++) {
        free(mat[i]);
    }
    free(mat);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

Single pass through matrix to check row lengths and uniqueness

✓ Linear Growth

Space Complexity

O(1)

Only using variables for calculations, no extra data structures

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

542 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler