Detect Cycles In 2d Grid - Leetcode Solution

Problem statement: Given a 2D grid of characters representing an image, find whether there is a cycle in the grid. A cycle is defined as a path of at least length 4 in the grid where all the vertices are same and the path is non-intersecting. The cycle must not include the same cell twice.

Example: Input: [['a','a','a','a'], ['a','b','b','a'], ['a','b','b','a'], ['a','a','a','a']] Output: true Explanation: The cycle exists: b -> b -> b -> b

Solution: To solve this problem, we can traverse each cell in the 2D grid and check for cycles starting from that cell. To avoid revisiting a cell, we can mark the visited cells with a different character. Then, we can perform a depth-first search from the current cell and check for cycles of length 4 or more. If a cycle is found, we update a boolean flag and return it.

Algorithm:

1. Traverse each cell in the 2D grid
2. Mark the current cell as visited by changing its value
3. Perform a depth-first search from the current cell
4. If the search results in a cycle of length 4 or more, update the flag and return it
5. Revert the marked cells back to their original values

Code:

class Solution: def containsCycle(self, grid: List[List[str]]) -> bool:

    def dfs(row, col, visited, parent, count):
        nonlocal cycle_found
        
        if (row, col) in visited:
            if count - visited[(row, col)] >= 4:
                cycle_found = True
            return
        
        visited[(row, col)] = count
        parent[(row, col)] = (prev_row, prev_col)
        
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            new_row, new_col = row + dx, col + dy
            if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]):
                if grid[new_row][new_col] == grid[row][col]:
                    if (new_row, new_col) != parent[(row, col)]:
                        dfs(new_row, new_col, visited, parent, count+1)
        
        visited.pop((row, col))
        

    cycle_found = False
    
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if grid[row][col] != None:
                visited = {}
                parent = {}
                dfs(row, col, visited, parent, 0)
                if cycle_found:
                    return True
                for key in visited:
                    grid[key[0]][key[1]] = None
    return False
                 

Time complexity: O(n * m), where n is the number of rows and m is the number of columns in the grid.

Space complexity: O(n * m), because we use a hash map to store the visited cells, which can have up to n * m entries.

1