Problem statement

https://leetcode.com/problems/detect-cycles-in-2d-grid/

Solution

Just classical loop detection problem: use dfs with parent node and check if we have loops.

Complexity

Time and space complexity is O(mn).

Code

class Solution:
    def containsCycle(self, grid):
        m, n, v = len(grid), len(grid[0]), set()
        self.Found = False
        
        def dfs(xp, yp, x, y):
            if self.Found: return
            if (x, y) in v: self.Found = True
            v.add((x, y))
            for dx, dy in [[0,1], [0,-1], [1,0], [-1,0]]:
                if not 0 <= x + dx < n or not 0 <= y + dy < m: continue
                if (x + dx, y + dy) == (xp, yp) or grid[y][x] != grid[y+dy][x+dx]: continue
                dfs(x, y, x+dx, y+dy)
        
        for x, y in product(range(n), range(m)):
            if (x, y) not in v:
                dfs(-1, -1, x, y)
        
        return self.Found