Matrix Similarity After Cyclic Shifts

Problem Description

Ah, the classic “Matrix Similarity After Cyclic Shifts” problem! It’s like trying to figure out if your friend’s scrambled eggs are still the same after they’ve been tossed around a bit. You know, just because they look different doesn’t mean they aren’t the same eggs!

In this problem, you are given a matrix and a number k. Your task is to determine if you can shift the rows of the matrix cyclically by k positions and still have the same matrix. Imagine you have a row of books on a shelf, and you want to see if you can rearrange them by shifting them around without actually changing the titles. Spoiler alert: if they end up looking the same, you’ve succeeded!

Code Solution


class Solution:
    def areSimilar(self, mat: list[list[int]], k: int) -> bool:
        n = len(mat[0])
        for row in mat:
            for j in range(n):
                if row[j] != row[(j + k) % n]:
                    return False
        return True

Approach

The approach taken in the code is straightforward. It iterates through each row of the matrix and checks if each element matches the element that would be in its position after a cyclic shift of k. If any element doesn’t match, it returns False. If all elements match after the checks, it returns True. It’s like checking if your scrambled eggs can still be identified as eggs after a good shake!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * m), where `n` is the number of rows and `m` is the number of columns in the matrix.
Space Complexity	O(1), as we are using a constant amount of space regardless of the input size.

Real-World Example

Imagine you’re at a party, and everyone is dancing in a circle. If you shift the positions of the dancers by k spots, can you still recognize the same group of people? If yes, then the matrix is similar after the cyclic shifts!