algoadvance

You are given two n x n binary matrices, grid1 and grid2. You need to determine if grid2 can be obtained by cyclically shifting the rows in grid1. A cyclic shift means moving the rightmost element of a row to the leftmost position and shifting all other elements one position to the right. You can perform the shift operation zero or more times on each row independently.

Return true if grid2 can be obtained by cyclically shifting rows of grid1, or false otherwise.

Clarifying Questions

  1. Can rows be shifted independently of each other or must all be shifted uniformly?
    • Rows can be shifted independently of each other.
  2. What is the range of the size n for the matrix?
    • Assume 1 <= n <= 50 for this problem.
  3. Are the matrices always square (i.e., n x n)?
    • Yes, the matrices are always n x n.
  4. Can the matrices contain values other than 0 and 1?
    • No, the matrices are binary matrices containing only 0s and 1s.

Strategy

The task is to verify if grid2 can be obtained by cyclically shifting rows of grid1. To do this, we should consider each row’s potential formations after any number of cyclic shifts. Each row in a matrix can produce n different rows after shifts.

Steps:

  1. Create a helper function to generate all possible cyclic shifts of a given row.
  2. For each row in grid2, check if it matches any possible shifted row from the corresponding row in grid1.
  3. If all rows in grid2 can match a cyclic shift of the corresponding row in grid1, return true; otherwise, return false.

Code

def shift_row(row, n):
    # Return a list of n cyclically shifted rows
    return [row[i:] + row[:i] for i in range(n)]

def can_cyclically_shift(grid1, grid2):
    n = len(grid1)
    
    for i in range(n):
        possible_shifts = shift_row(grid1[i], n)
        if grid2[i] not in possible_shifts:
            return False
    
    return True

# Example Usage
grid1 = [
    [1, 0, 1],
    [1, 1, 0],
    [0, 1, 1]
]

grid2 = [
    [1, 1, 1],
    [1, 0, 1],
    [0, 1, 1]
]

print(can_cyclically_shift(grid1, grid2))

Time Complexity

  1. Shift Generation: Generating all shifts for all rows involves looping over each row and generating n cyclic shifts, which takes O(n^2) for each row.
  2. Checking Shifts: Each check to find if a row in grid2 matches any of the n shifted versions of the row in grid1 takes O(n^2) comparisons (n rows, and each has at most n possible rows to match).

Hence, the total time complexity is O(n^3), which is manageable given the constraint 1 <= n <= 50.

Try our interview co-pilot at AlgoAdvance.com