We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Matrix Similarity After Cyclic Shifts

Difficulty: Easy

Problem Description

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.

Key Insights

  • Even-indexed rows undergo left shifts, while odd-indexed rows undergo right shifts.
  • After k shifts, we can determine the effective number of shifts needed by taking k modulo the number of columns.
  • If the rows are identical after the shifts, the original matrix and modified matrix are the same.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(1)

Solution

To determine if the matrix is identical to its original state after k cyclic shifts, we will:

  1. Calculate the effective shifts for even and odd indexed rows using modulo with the number of columns.
  2. Shift the even indexed rows to the left and the odd indexed rows to the right accordingly.
  3. Compare the modified matrix with the original matrix.

The algorithm primarily uses list operations to modify the rows in place without needing additional data structures.

Code Solutions

def are_matrices_identical(mat, k):
    rows = len(mat)
    if rows == 0:
        return True
    cols = len(mat[0])
    
    # Calculate effective shifts
    left_shift = k % cols
    right_shift = (-k) % cols  # Right shift is equivalent to negative left shift
    
    # Create a new matrix to store the modified version
    modified = [row[:] for row in mat]
    
    for i in range(rows):
        if i % 2 == 0:  # Even-indexed rows
            modified[i] = modified[i][left_shift:] + modified[i][:left_shift]
        else:  # Odd-indexed rows
            modified[i] = modified[i][right_shift:] + modified[i][:right_shift]

    return modified == mat
← Back to All Questions