We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Detect Cycles in 2D Grid

Difficulty: Medium

Problem Description

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. You cannot move to the cell that you visited in your last move. Return true if any cycle of the same value exists in grid, otherwise, return false.

Key Insights

  • A cycle must consist of at least four cells with the same value.
  • Movement is restricted to adjacent cells (up, down, left, right) that contain the same character.
  • The last visited cell cannot be revisited in the current step to maintain the cycle condition.
  • Depth-First Search (DFS) can be used to explore the grid and detect cycles.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid, as each cell is visited at most once. Space Complexity: O(m * n) for the recursion stack in the worst case.

Solution

To solve the problem, we can use a Depth-First Search (DFS) approach. We will iterate through each cell in the grid, and for each cell, we will initiate a DFS if it has not been visited. During the DFS, we will keep track of the previous cell to avoid immediately returning to it. If we reach a cell that we have already visited and it is not the immediate previous cell, we check the length of the cycle formed. If the cycle length is 4 or more, we return true. If no cycles are found after exploring all cells, we return false.

Code Solutions

def containsCycle(grid):
    if not grid:
        return False
    
    m, n = len(grid), len(grid[0])
    visited = [[False] * n for _ in range(m)]
    
    def dfs(x, y, px, py, char, length):
        if visited[x][y]:
            return length >= 4
        
        visited[x][y] = True
        
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == char:
                if (nx, ny) != (px, py) and dfs(nx, ny, x, y, char, length + 1):
                    return True
        
        return False
    
    for i in range(m):
        for j in range(n):
            if not visited[i][j] and dfs(i, j, -1, -1, grid[i][j], 1):
                return True
    
    return False
← Back to All Questions