Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
Given a 2D array of characters grid of size m x n, you need to find if there exists any cycle consisting of the same value in grid.
A cycle is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it - in one of the four directions (up, down, left, or right), if it has the same value of the current cell.
Also, you cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.
Return true if any cycle of the same value exists in grid, otherwise, return false.
Example 1:
Input: grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]] Output: true Explanation: There are two valid cycles shown in different colors in the image below:
Example 2:
Input: grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]] Output: true Explanation: There is only one valid cycle highlighted in the image below:
Example 3:
Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]] Output: false
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 500grid consists only of lowercase English letters.Problem summary: Given a 2D array of characters grid of size m x n, you need to find if there exists any cycle consisting of the same value in grid. A cycle is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it - in one of the four directions (up, down, left, or right), if it has the same value of the current cell. Also, you cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell. Return true if any cycle of the same value exists in grid, otherwise, return false.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Union-Find
[["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
[["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
[["a","b","b"],["b","z","b"],["b","b","a"]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1559: Detect Cycles in 2D Grid
class Solution {
public boolean containsCycle(char[][] grid) {
int m = grid.length, n = grid[0].length;
boolean[][] vis = new boolean[m][n];
final int[] dirs = {-1, 0, 1, 0, -1};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (!vis[i][j]) {
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[] {i, j, -1, -1});
vis[i][j] = true;
while (!q.isEmpty()) {
int[] p = q.poll();
int x = p[0], y = p[1], px = p[2], py = p[3];
for (int k = 0; k < 4; ++k) {
int nx = x + dirs[k], ny = y + dirs[k + 1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] != grid[x][y] || (nx == px && ny == py)) {
continue;
}
if (vis[nx][ny]) {
return true;
}
q.offer(new int[] {nx, ny, x, y});
vis[nx][ny] = true;
}
}
}
}
}
}
return false;
}
}
// Accepted solution for LeetCode #1559: Detect Cycles in 2D Grid
func containsCycle(grid [][]byte) bool {
m, n := len(grid), len(grid[0])
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
dirs := []int{-1, 0, 1, 0, -1}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if !vis[i][j] {
q := [][]int{{i, j, -1, -1}}
vis[i][j] = true
for len(q) > 0 {
p := q[0]
q = q[1:]
x, y, px, py := p[0], p[1], p[2], p[3]
for k := 0; k < 4; k++ {
nx, ny := x+dirs[k], y+dirs[k+1]
if nx >= 0 && nx < m && ny >= 0 && ny < n {
if grid[nx][ny] != grid[x][y] || (nx == px && ny == py) {
continue
}
if vis[nx][ny] {
return true
}
q = append(q, []int{nx, ny, x, y})
vis[nx][ny] = true
}
}
}
}
}
}
return false
}
# Accepted solution for LeetCode #1559: Detect Cycles in 2D Grid
class Solution:
def containsCycle(self, grid: List[List[str]]) -> bool:
m, n = len(grid), len(grid[0])
vis = [[False] * n for _ in range(m)]
dirs = (-1, 0, 1, 0, -1)
for i, row in enumerate(grid):
for j, x in enumerate(row):
if vis[i][j]:
continue
vis[i][j] = True
q = [(i, j, -1, -1)]
while q:
x, y, px, py = q.pop()
for dx, dy in pairwise(dirs):
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
if grid[nx][ny] != grid[i][j] or (nx == px and ny == py):
continue
if vis[nx][ny]:
return True
vis[nx][ny] = True
q.append((nx, ny, x, y))
return False
// Accepted solution for LeetCode #1559: Detect Cycles in 2D Grid
impl Solution {
pub fn contains_cycle(grid: Vec<Vec<char>>) -> bool {
let m = grid.len();
let n = grid[0].len();
let mut vis = vec![vec![false; n]; m];
let dirs = vec![-1, 0, 1, 0, -1];
for i in 0..m {
for j in 0..n {
if !vis[i][j] {
let mut q = vec![(i as isize, j as isize, -1, -1)];
vis[i][j] = true;
while !q.is_empty() {
let (x, y, px, py) = q.pop().unwrap();
for k in 0..4 {
let nx = x + dirs[k];
let ny = y + dirs[k + 1];
if nx >= 0 && nx < m as isize && ny >= 0 && ny < n as isize {
let nx = nx as usize;
let ny = ny as usize;
if grid[nx][ny] != grid[x as usize][y as usize]
|| (nx == px as usize && ny == py as usize)
{
continue;
}
if vis[nx][ny] {
return true;
}
q.push((nx as isize, ny as isize, x, y));
vis[nx][ny] = true;
}
}
}
}
}
}
false
}
}
// Accepted solution for LeetCode #1559: Detect Cycles in 2D Grid
function containsCycle(grid: string[][]): boolean {
const [m, n] = [grid.length, grid[0].length];
const vis: boolean[][] = Array.from({ length: m }, () => Array(n).fill(false));
const dirs = [-1, 0, 1, 0, -1];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (!vis[i][j]) {
const q: [number, number, number, number][] = [[i, j, -1, -1]];
vis[i][j] = true;
for (const [x, y, px, py] of q) {
for (let k = 0; k < 4; k++) {
const [nx, ny] = [x + dirs[k], y + dirs[k + 1]];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] !== grid[x][y] || (nx === px && ny === py)) {
continue;
}
if (vis[nx][ny]) {
return true;
}
q.push([nx, ny, x, y]);
vis[nx][ny] = true;
}
}
}
}
}
}
return false;
}
Use this to step through a reusable interview workflow for this problem.
Track components with a list or adjacency matrix. Each union operation may need to update all n elements’ component labels, giving O(n) per union. For n union operations total: O(n²). Find is O(1) with direct lookup, but union dominates.
With path compression and union by rank, each find/union operation takes O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant. Space is O(n) for the parent and rank arrays. For m operations on n elements: O(m × α(n)) total.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.