2946. Matrix Similarity After Cyclic Shifts

EasyView on LeetCode

Array Matrix Simulation

Time: O(n*m)

Space: O(1)

Intuition

Check if string has "beautiful" splits: first part is prefix of second, or second is prefix of third.

Algorithm

1For each split point (i, j): check if s[0..i-1] is prefix of s[i..j-1] OR s[i..j-1] is prefix of s[j..].

Common Pitfalls

•O(n^3) brute force. Optimize with Z-array or KMP prefix function for O(n^2).

2946.cs

// Approach: After k cyclic shifts, odd rows shift right and even rows shift left (or vice versa).
// A row is unchanged after k shifts only if it has period k, i.e. every element equals the one k
// positions ahead (mod n). Check each element in each row against its k-shifted counterpart.
// Time: O(n*m) Space: O(1)
public class Solution
{
    public bool AreSimilar(int[][] mat, int k)
    {
        int n = mat[0].Length;
        foreach (var row in mat)
        {
            for (int j = 0; j < n; ++j)
            {
                if (row[j] != row[(j + k) % n])
                    return false;
            }
        }

        return true;
    }
}

Was this solution helpful?