Detect Cycles in 2D Grid

Medium
457.

Detect Cycles in 2D Grid

Detect Cycles in 2D Grid is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Nutanix interviews.

You are given a grid of lowercase letters, one string per row. A cycle is a path of length 4 or more that starts and ends on the same cell, moves only between side-adjacent cells holding the same letter, and never steps straight back to the cell it just came from.

Return true if the grid contains any cycle.

Example 1

Input
grid = ["aaaa","abca","aada","aaaa"]
Output
true

Example 2

Input
grid = ["aaaa","abca","aaaa"]
Output
true

Example 3

Input
grid = ["ab","ba"]
Output
false

Constraints

  • 1 <= grid.length <= 12
  • All rows have the same length, between 1 and 12.
  • The grid contains only lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} grid
 * @return {boolean}
 */
var containsCycle = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Detect Cycles in 2D Grid — Solution in Python, Java & C++

Detect Cycles in 2D Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Detect Cycles in 2D Grid is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Nutanix interviews.

Problem statement

You are given a grid of lowercase letters, one string per row. A cycle is a path of length 4 or more that starts and ends on the same cell, moves only between side-adjacent cells holding the same letter, and never steps straight back to the cell it just came from.

Return true if the grid contains any cycle.

Example 1

Input: grid = ["aaaa","abca","aada","aaaa"]
Output: true

Example 2

Input: grid = ["aaaa","abca","aaaa"]
Output: true

Example 3

Input: grid = ["ab","ba"]
Output: false

Constraints

  • 1 <= grid.length <= 12
  • All rows have the same length, between 1 and 12.
  • The grid contains only lowercase English letters.

Hints for Detect Cycles in 2D Grid

  1. Hint 1

    Explore each same-letter region with a DFS, carrying the cell you arrived from.

  2. Hint 2

    Skip that parent cell so a simple back-and-forth is not mistaken for a cycle.

  3. Hint 3

    Reaching an already-visited cell that is not the parent means a cycle exists.

How to solve Detect Cycles in 2D Grid

DFS each same-letter region carrying the parent cell; reaching an already-visited cell that is not the parent means a cycle.

Approach

  1. For each unvisited cell, DFS with (cell, parent).
  2. For each same-letter neighbour other than the parent: return true if visited, else mark and push.
  3. Return false.

Why it works

In an undirected graph a DFS back edge to a non-parent visited node closes a cycle, and every grid cycle has length ≥ 4 automatically since the grid is bipartite.

Complexity

  • Time — O(m · n)
  • Space — O(m · n)

Pitfalls

  • Skipping the parent is what prevents a single edge from being seen as a cycle.

Reference solution

Python

def containsCycle(grid) -> bool:
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if seen[r][c]:
                continue
            letter = grid[r][c]
            stack = [(r, c, -1, -1)]
            seen[r][c] = True
            while stack:
                cr, cc, pr, pc = stack.pop()
                for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
                    if not (0 <= nr < rows and 0 <= nc < cols):
                        continue
                    if grid[nr][nc] != letter or (nr == pr and nc == pc):
                        continue
                    if seen[nr][nc]:
                        return True
                    seen[nr][nc] = True
                    stack.append((nr, nc, cr, cc))
    return False

Java

public static boolean containsCycle(String[] grid) {
    int rows = grid.length, cols = grid[0].length();
    boolean[][] seen = new boolean[rows][cols];
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (seen[r][c]) continue;
            char letter = grid[r].charAt(c);
            Deque<int[]> stack = new ArrayDeque<>();
            stack.push(new int[]{r, c, -1, -1});
            seen[r][c] = true;
            while (!stack.isEmpty()) {
                int[] cell = stack.pop();
                for (int d = 0; d < 4; d++) {
                    int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
                    if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                    if (grid[nr].charAt(nc) != letter) continue;
                    if (nr == cell[2] && nc == cell[3]) continue;
                    if (seen[nr][nc]) return true;
                    seen[nr][nc] = true;
                    stack.push(new int[]{nr, nc, cell[0], cell[1]});
                }
            }
        }
    }
    return false;
}

C++

bool containsCycle(vector<string>& grid) {
    int rows = (int) grid.size(), cols = (int) grid[0].size();
    vector<vector<bool>> seen(rows, vector<bool>(cols, false));
    int dr[4] = {1, -1, 0, 0};
    int dc[4] = {0, 0, 1, -1};
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (seen[r][c]) continue;
            char letter = grid[r][c];
            vector<array<int,4>> stack;
            stack.push_back({r, c, -1, -1});
            seen[r][c] = true;
            while (!stack.empty()) {
                array<int,4> cell = stack.back();
                stack.pop_back();
                for (int d = 0; d < 4; d++) {
                    int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
                    if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                    if (grid[nr][nc] != letter) continue;
                    if (nr == cell[2] && nc == cell[3]) continue;
                    if (seen[nr][nc]) return true;
                    seen[nr][nc] = true;
                    stack.push_back({nr, nc, cell[0], cell[1]});
                }
            }
        }
    }
    return false;
}

JavaScript

var containsCycle = function(grid) {
    const rows = grid.length, cols = grid[0].length;
    const seen = [];
    for (let r = 0; r < rows; r++) {
        const row = [];
        for (let c = 0; c < cols; c++) row.push(false);
        seen.push(row);
    }
    const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (seen[r][c]) continue;
            const letter = grid[r].charAt(c);
            const stack = [[r, c, -1, -1]];
            seen[r][c] = true;
            while (stack.length > 0) {
                const cell = stack.pop();
                for (let d = 0; d < 4; d++) {
                    const nr = cell[0] + dr[d], nc = cell[1] + dc[d];
                    if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                    if (grid[nr].charAt(nc) !== letter) continue;
                    if (nr === cell[2] && nc === cell[3]) continue;
                    if (seen[nr][nc]) return true;
                    seen[nr][nc] = true;
                    stack.push([nr, nc, cell[0], cell[1]]);
                }
            }
        }
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)