Abstract / Summary

Check if moving through a grid by following arrows forms a loop.

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 53% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Depth First Search
• Matrix
• Union Find

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 implementation determines whether a rectangular grid of characters contains a cycle formed by adjacent cells of the same character. A cycle is defined as a closed path of length four or more that returns to a previously visited cell without immediately back-tracking to the predecessor. The algorithm explores the grid using depth-first search (DFS) while tracking visited cells globally to avoid redundant work.

Core Logic

Grid dimensions

width  = len(grid[0])
height = len(grid)

The width and height are computed once, allowing constant-time boundary checks throughout the search.

Direction encoding

deltas = [ +1, 0, -1, 0 ]   # encodes (0,1),(1,0),(0,-1),(-1,0)

A compact list stores the four orthogonal moves. By rotating the values inside the loop, the code derives dx and dy without allocating separate tuples for each direction.

Global visited set

known = set()   # visited cells

All cells that have been examined in any DFS branch are stored in a set of coordinate tuples. This set prevents revisiting regions that have already been proven not to contain a cycle, reducing the overall number of recursive calls.

Recursive DFS (deeper)

def deeper(x, y, oldx = -1, oldy = -1):
    if (x, y) in known:
        return True
    known.add((x, y))

    dx = dy = 0
    for d in deltas:
        dy = dx
        dx = d

        nx = x + dx
        ny = y + dy
        if nx == oldx and ny == oldy:
            continue
        if 0 <= nx < width and 0 <= ny < height and grid[ny][nx] == grid[y][x]:
            if deeper(nx, ny, x, y):
                return True
    return False

The function receives the current cell (x, y) and the coordinates of the cell from which it arrived (oldx, oldy). The first test checks whether the current cell has already been recorded in known. Encountering a known cell indicates that a path has looped back to a previously visited location, satisfying the cycle condition. The cell is then added to known to mark it as explored.

The inner loop iterates over the four possible moves. By swapping dx and dy before each assignment, the code generates the orthogonal offsets without extra data structures. The continue statement skips the immediate back-track to the predecessor, which would otherwise be interpreted as a trivial two-cell “cycle” that the problem definition excludes.

Boundary checks (0 <= nx < width and 0 <= ny < height) guarantee that the search stays inside the grid. The color comparison (grid[ny][nx] == grid[y][x]) ensures that only cells with the same character are considered part of the same component. When a neighbor satisfies all constraints, the recursion proceeds with the neighbor as the new current cell and the current cell as its predecessor. If any recursive call returns True, the function propagates the success upward.

If the loop finishes without finding a cycle, the function returns False, indicating that the current DFS branch did not encounter a repeated cell.

Initiating DFS from each component

for y in range(height):
    for x in range(width):
        if (x, y) not in known and deeper(x, y):
            return True
return False

The double loop scans the grid row-by-row. For each cell that has not yet been visited, it launches a new DFS. Because known accumulates cells from previous searches, each connected component is explored exactly once. If any invocation of deeper reports a cycle, the outer function returns True immediately. If the entire grid is processed without detecting a cycle, the function returns False.

Edge Cases Handled

When the grid consists of a single row or a single column, the boundary checks prevent out-of-range neighbor calculations, and the back-track avoidance ensures that a two-cell back-and-forth does not falsely trigger a cycle.

If the grid contains isolated cells (no adjacent same-colored neighbors), the DFS adds the cell to known and terminates without recursion, correctly reporting the absence of a cycle.

Grids where all cells share the same character are processed efficiently: the first DFS will traverse the entire grid, marking every cell as known. Any later start positions are skipped because they are already in known, preventing unnecessary repeated traversals.

The algorithm also correctly handles grids with multiple disconnected components of the same character. Each component is explored independently, and a cycle in any component leads to an early return.

Performance Optimizations

The use of a single global known set eliminates the need for a separate visited structure per DFS call, thereby reducing memory overhead and avoiding repeated allocation of temporary containers.

Encoding the four directions in a flat list and deriving dx/dy through variable swapping avoids the creation of tuple objects for each neighbor, which can be a noticeable cost in tight loops.

Early termination is built into both the recursive function and the outer scanning loops. As soon as a cycle is discovered, the recursion unwinds and the outer function returns, preventing further exploration of the remaining grid.

By checking if (x, y) not in known before launching a new DFS, the algorithm guarantees that each connected component is visited only once, yielding linear work relative to the number of cells.

The boundary checks are performed before the character comparison, ensuring that the more expensive string equality is only evaluated for valid neighbor coordinates.

Overall, the design balances clarity with low-level efficiency, leveraging Python’s set membership tests and minimalistic neighbor generation to achieve fast detection of cycles in typical grid sizes.

Imagine you are looking at a big grid of colorful square tiles on the floor. The goal is to see if any path of the same color makes a closed loop, like a circle that leads back to where it started.

To solve this, the code acts like a tiny explorer walking across the grid. It keeps a secret notebook called known where it writes down the address of every tile it has already visited.

The explorer starts at the top left corner and begins moving to a neighbor tile only if that neighbor has the exact same color as the current one. If the explorer finds a tile that is already written in the notebook, that means a circle has been formed.

However, the explorer is very careful. It remembers exactly which tile it just came from, so it does not count walking backward as finding a circle. It wants to find a real, meaningful path that travels through different tiles before meeting itself again.

The code repeats this process for every single tile in the grid. It checks every square to make sure no hidden loops are hiding anywhere. If it ever lands on a tile that is already in the notebook while looking for a friend of the same color, it knows a cycle exists. It keeps searching until it has checked everything or found a loop.

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	C++		Java	Python				TS
	WalkCCC	C++		Java
	leetcode.ca	C++	JS	Java	Python		Go	Rust	TS
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	FelixFan1122			Java
	fsq	C++
	JoshCrozier		JS
	keineahnung2345	C++
	lkwq007				Python
	suxrobGM					C#
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
FelixFan1122	Java
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
wisdompeak	C++
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