Detect Cycles in 2D Grid
Medium · Graphs · Array · Depth-First Search · Breadth-First Search · Union Find · Matrix
Problem
You are given an m x n grid of lowercase letters. From a cell you may step up, down, left or right to a neighboring cell that holds the same letter, but you may not step straight back to the cell you just came from.
A cycle is a path of length 4 or more that starts and ends at the same cell under these rules. Return true if any cycle of identical letters exists in the grid, and false otherwise.
Examples
Input: grid = [["b","b","a"],["b","b","a"],["a","a","a"]] Output: true
The four b cells in the top-left form a 2 × 2 loop.
Input: grid = [["a","b","a"],["a","a","a"]] Output: false
The a cells form a U with no loop, and the lone b cannot form one.
Input: grid = [["c","c","c"],["c","d","c"],["c","c","c"]] Output: true
The c cells form a ring around the d.
Constraints
- m == len(grid), n == len(grid[i])
- 1 <= m, n <= 500
- grid holds lowercase English letters only
Approaches
- Baseline: try removing each edge — time O((m · n)²), space O(m · n)
Follow-up
Why does the rule “a path of length 4 or more” never matter? In a grid graph the shortest cycle is a 2 × 2 square, which already has length 4. See the use cases for counting how many regions contain a loop, and for the same test on an undirected graph given as an edge list.
Related problems
Start free on Cariara · Coding problems · System design studio
