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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Matrix Similarity After Cyclic Shifts

Number: 3215

Difficulty: Easy

Paid? No

Companies: Salesforce

Problem Description

Given an m x n matrix, perform k cyclic shifts: even-indexed rows are shifted to the left and odd-indexed rows are shifted to the right. Determine if the matrix after k steps is identical to the original matrix.

Key Insights

  • Each row’s behavior depends solely on its index (even-indexed vs odd-indexed).
  • Shifting cyclically by k positions is equivalent to shifting by (k mod n) positions when there are n columns.
  • For even-indexed rows, a left shift by shift positions must return the original row for similarity.
  • For odd-indexed rows, a right shift by shift positions is equivalent to a left shift by (n - shift) positions.
  • If the cyclically shifted row does not match the original row for any row, then the final matrix is not identical.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Space Complexity: O(n) for the temporary array used in comparing shifted rows.

Solution

For each row in the matrix:

  1. Compute the effective shift value as shift = k mod n.
  2. For even-indexed rows, shift left by shift positions.
  3. For odd-indexed rows, shift right by shift positions (or equivalently left by (n - shift) positions).
  4. Compare the shifted row with the original row.
  5. Return false immediately if any row does not match; return true if all rows match.

The approach uses basic list slicing (or equivalent in other languages) to simulate the cyclic shift without needing extra space to store a transformed matrix, aside from temporary variables.

Code Solutions

# Python solution with line-by-line comments

def checkMatrixSimilarity(mat, k):
    # Get the number of rows and columns
    m = len(mat)
    n = len(mat[0])
    # For each row in the matrix, check if the cyclic shift returns original row
    for i in range(m):
        # Effective shift computed by modulo length of the row
        shift = k % n
        # If the row is even-indexed, we perform left shift by `shift`
        if i % 2 == 0:
            shifted_row = mat[i][shift:] + mat[i][:shift]
        else:
            # For odd indexed rows, right shift by `shift` is equivalent to left shift by (n - shift)
            effective_left_shift = (n - shift) % n
            shifted_row = mat[i][effective_left_shift:] + mat[i][:effective_left_shift]
        # If shifted row does not equal original row, return False
        if shifted_row != mat[i]:
            return False
    return True

# Example Usage:
print(checkMatrixSimilarity([[1,2,3],[4,5,6],[7,8,9]], 4))  # Expected output: False
print(checkMatrixSimilarity([[1,2,1,2],[5,5,5,5],[6,3,6,3]], 2))  # Expected output: True
← Back to All Questions