Abstract / Summary

Given a square matrix, determine if all its cyclic row shifts are similar to the original matrix.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 58% (40k+ submissions).

Typical patterns to solve this problem:

• Array
• Math
• Matrix
• Simulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution.areSimilar method determines whether every row of a two-dimensional integer matrix satisfies a specific rotational similarity condition. The condition depends on the row index: rows with an odd index must match their own values after a rightward shift of k positions, while rows with an even index must match after a leftward shift of k positions. The method returns True only when all rows meet their respective criteria.

Key Steps

Determine matrix width and handle trivial full rotations

The first operation extracts the number of columns from the first row and stores it in width. A quick check follows: if k is an exact multiple of width, any rotation brings the row back to its original configuration, making the similarity condition automatically satisfied for every row. In this case the method returns True without further processing.

width = len(mat[0])
if k % width == 0:  # full rotations
    return True

Iterate over rows and columns while distinguishing parity

The method proceeds with a double loop. The outer loop enumerates each row together with its index i. The inner loop walks through each column position x. The parity of the row index (i & 1) decides which direction the rotation should be applied for the current row.

for i, row in enumerate(mat):
    for x in range(width):
        if i & 1:  # odd
            ...
        else:     # even
            ...

Compare elements using the appropriate offset

For odd rows the element at column x must equal the element that appears k positions to the right, which is accessed via (x + k) % width. For even rows the element must equal the one k positions to the left, accessed via (x - k) % width. If any comparison fails, the method returns False immediately, aborting further checks.

if i & 1:  # odd
    if row[x] != row[(x + k) % width]:
        return False
else:     # even
    if row[x] != row[(x - k) % width]:
        return False

Conclude after successful verification of all rows

If the loops complete without triggering a mismatch, the method reaches the final statement and returns True, indicating that every row conforms to its required rotational similarity.

return True

Edge Cases Handled

The implementation explicitly addresses the situation where the rotation distance k equals a full cycle of the row length. By checking k % width == 0, it treats any multiple of the row width as a no-op rotation, guaranteeing a True result without examining the matrix contents.

When k is zero, the modulo operation still yields zero, and the comparison reduces to row[x] != row[x], which never triggers a mismatch, so the method correctly returns True for any matrix.

The parity test i & 1 correctly distinguishes between odd and even row indices, ensuring that the direction of the offset aligns with the specification for each row type. The modulo arithmetic (x + k) % width and (x - k) % width safely wraps indices around the row boundaries, handling cases where the offset would otherwise exceed the column range or become negative.

Performance Optimizations

The early exit on full rotations (k % width == 0) eliminates the need for any per-element work when the answer is known a priori, saving time for large matrices with trivial rotation distances.

The use of a bitwise AND (i & 1) to test row parity is marginally faster than a modulo operation, reducing overhead inside the innermost loop.

Modulo operations are performed only once per element comparison, and the indices are computed directly inside the conditional checks, avoiding the creation of auxiliary data structures or temporary lists.

The method returns False at the first detected mismatch, preventing unnecessary iteration over the remaining rows and columns once the similarity condition is violated. This short-circuit behavior provides a best-case performance gain when the matrix fails the test early.

Think of the grid as a collection of rows filled with colorful blocks. Every single row is like a little train, and the code follows a set of rules to see if moving these trains around leaves them looking exactly the same as they did at the start.

First, the code checks how wide the trains are. If the number of shifts is a perfect match for the length of the row, the trains end up in their original spots, which means they are definitely similar.

Next, the code looks at every single row one by one. It uses the row number to decide which way to shift the blocks. If the row number is odd, it slides the blocks to the left. If the row number is even, it slides the blocks to the right.

As it slides them, it checks to see if the block at the new spot is the same color as the block at the old spot. If it finds even one block that does not match after the shuffle, then the trains are not similar. If it finishes checking every block in every row and finds that everything matches perfectly, then the grid is considered similar after the movement.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	C++		Python		TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	Rust	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
	varunu28		Java
	withaarzoo			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
varunu28	Java
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality