Detect cycles in 2d grid

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

52.5% acceptance

Feb 25, 2026

1323

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 the last step. 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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn contains_cycle(grid: Vec<Vec<char>>) -> bool {
    let m = grid.len();
    let n = grid[0].len();
    let mut visited = vec![vec![false; n]; m];

    fn dfs(
      grid: &Vec<Vec<char>>,
      visited: &mut Vec<Vec<bool>>,
      r: usize,
      c: usize,
      pr: usize,
      pc: usize,
      ch: char,
    ) -> bool {
      if visited[r][c] {
        return true;
      }
      visited[r][c] = true;
      let dirs: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
      let m = grid.len();
      let n = grid[0].len();
      for (dr, dc) in dirs {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr < 0 || nr >= m as i32 || nc < 0 || nc >= n as i32 {
          continue;
        }
        let nr = nr as usize;
        let nc = nc as usize;
        if nr == pr && nc == pc {
          continue; // don't go back to parent
        }
        if grid[nr][nc] != ch {
          continue;
        }
        if dfs(grid, visited, nr, nc, r, c, ch) {
          return true;
        }
      }
      false
    }

    for r in 0..m {
      for c in 0..n {
        if !visited[r][c] {
          if dfs(&grid, &mut visited, r, c, usize::MAX, usize::MAX, grid[r][c]) {
            return true;
          }
        }
      }
    }
    false
  }
}