Scale Engineer

Detect Cycles in 2D Grid

Med
#1435Time: O(m * n), where `m` is the number of rows and `n` is the number of columns. Each cell in the grid is visited at most once during the entire process.Space: O(m * n). This space is used for the `visited` array (O(m * n)) and the recursion call stack. In the worst-case scenario of a path that traverses every cell, the stack depth can be up to O(m * n).1 company
Algorithms
Depth-First SearchBreadth-First SearchUnion Find
Data structures
ArrayMatrix
Companies
Nutanix

Prompt

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.length
  • n == grid[i].length
  • 1 <= m, n <= 500
  • grid consists only of lowercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach models the grid as an undirected graph. Each cell (r, c) is a node, and an edge exists between two adjacent cells if they contain the same character. The problem then becomes finding a cycle in this graph. We can use Depth First Search (DFS) to traverse the graph and detect cycles. We iterate through every cell of the grid. If a cell hasn't been visited, we start a DFS from it. During the traversal, if we encounter a visited node that is not the immediate parent of the current node in the DFS tree, we have found a back edge, which indicates a cycle.

Algorithm

  • Initialize a visited[m][n] 2D boolean array, marking all cells as not visited.
  • Iterate through each cell (r, c) of the grid from (0, 0) to (m-1, n-1).
  • If the current cell (r, c) has not been visited (visited[r][c] is false), it signifies the start of a new, unexplored connected component.
  • Start a Depth First Search (DFS) from this cell. The DFS function will be of the form dfs(row, col, parent_row, parent_col).
  • The dfs function:
    1. Marks the current cell (row, col) as visited.
    2. Iterates through its four neighbors (up, down, left, right).
    3. For each neighbor (nr, nc): a. It must be within the grid boundaries. b. It must have the same character as the starting cell of the current component. c. It must not be the immediate parent cell from which we arrived at (row, col). This prevents trivial 1-edge-back cycles. d. If the neighbor (nr, nc) has already been visited (and is not the parent), a cycle has been detected. Return true. e. If the neighbor is valid but not visited, make a recursive call: dfs(nr, nc, row, col). If this call returns true, propagate the result by returning true immediately.
  • If the DFS completes for a component without finding a cycle, it returns false.
  • If the main loop finishes checking all cells and components without any DFS returning true, then no cycles exist in the grid. Return false.

Walkthrough

To implement this, we'll use a 2D boolean array, visited, of the same size as the grid to keep track of visited cells across all traversals. We'll iterate through each cell (r, c). If visited[r][c] is false, we start a new DFS traversal for the connected component of cells with the character grid[r][c].

The DFS function, say hasCycle(r, c, parent_r, parent_c), takes the current cell's coordinates and its parent's coordinates. This parent information is crucial to ensure we don't immediately travel back to the cell we just came from. Inside the DFS, we first mark the current cell as visited. Then, we explore its four neighbors. For any neighbor that has the same character, is not the parent, and has already been visited, we've found a cycle. If a neighbor is valid but unvisited, we recurse on it. If any recursive call finds a cycle, we propagate true up the call stack. If the entire grid is scanned and no cycle is found, we return false.

The problem states that a cycle must have a length of 4 or more. In a 2D grid where movement is restricted to four directions, the graph formed is bipartite. The smallest possible cycle in a bipartite graph has a length of 4 (e.g., a 2x2 square). Therefore, any cycle detected by this standard algorithm will automatically satisfy the length constraint.

class Solution {    private int m, n;    private char[][] grid;    private boolean[][] visited;    private int[] dr = {0, 0, 1, -1};    private int[] dc = {1, -1, 0, 0};     public boolean containsCycle(char[][] grid) {        this.m = grid.length;        this.n = grid[0].length;        this.grid = grid;        this.visited = new boolean[m][n];         for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (!visited[i][j]) {                    if (dfs(i, j, -1, -1, grid[i][j])) {                        return true;                    }                }            }        }        return false;    }     private boolean dfs(int r, int c, int pr, int pc, char targetChar) {        visited[r][c] = true;         for (int i = 0; i < 4; i++) {            int nr = r + dr[i];            int nc = c + dc[i];             if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == targetChar) {                if (nr == pr && nc == pc) {                    continue; // Don't go back to the parent immediately                }                if (visited[nr][nc]) {                    return true; // Found a cycle                }                if (dfs(nr, nc, r, c, targetChar)) {                    return true;                }            }        }        return false;    }}

Complexity

Time

O(m * n), where `m` is the number of rows and `n` is the number of columns. Each cell in the grid is visited at most once during the entire process.

Space

O(m * n). This space is used for the `visited` array (O(m * n)) and the recursion call stack. In the worst-case scenario of a path that traverses every cell, the stack depth can be up to O(m * n).

Trade-offs

Pros

  • The approach is intuitive and directly translates the problem into a standard graph traversal algorithm.

  • It is relatively easy to implement using recursion.

Cons

  • The recursive nature can lead to a StackOverflowError on very large grids with long, snake-like paths, as the recursion depth can become very large.

  • The space complexity includes the recursion stack, which can be significant in the worst-case scenario.

Solutions

class Solution {private  int[] p;public  boolean containsCycle(char[][] grid) {    int m = grid.length;    int n = grid[0].length;    p = new int[m * n];    for (int i = 0; i < p.length; ++i) {      p[i] = i;    }    int[] dirs = {0, 1, 0};    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        for (int k = 0; k < 2; ++k) {          int x = i + dirs[k];          int y = j + dirs[k + 1];          if (x < m && y < n && grid[i][j] == grid[x][y]) {            if (find(x * n + y) == find(i * n + j)) {              return true;            }            p[find(x * n + y)] = find(i * n + j);          }        }      }    }    return false;  }private  int find(int x) {    if (p[x] != x) {      p[x] = find(p[x]);    }    return p[x];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem