Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1559.html

Solution 1. DFS

We can use DFS for each A[x][y] to see if we can form a circle from A[x][y].

Let seen[x][y] be the length of the sequence containing the same character ending with A[x][y].

In the DFS, assume the next location we want to visit is <a, b>.

We shouldn’t visit a, b if either of these is true:

  • a, b are out-of-bound.
  • A[a][b] != A[x][y]
  • seen[a][b] != 0 and seen[x][y] - seen[a][b] < 3, meaning that we’ve visited A[a][b] in the sequence and the distance between A[a][b] and A[x][y] is too small to form a valid circle.

Once we find a <a, b> pair satisfying seen[a][b] && seen[x][y] - seen[a][b] >= 3, we’ve found a valid circle from A[a][b] to A[x][y] with length more than or equal to 4, and we can return true.

// OJ: https://leetcode.com/problems/detect-cycles-in-2d-grid/
// Time: O(MN)
// Space: O(MN)
class Solution {
    int seen[501][501] = {}, M, N, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
    bool dfs(vector<vector<char>> &G, int i, int j, int len = 1) {
        seen[i][j] = len;
        for (auto &[dx, dy] : dirs) {
            int x = i + dx, y = j + dy;
            if (x < 0 || x >= M || y < 0 || y >= N || G[x][y] != G[i][j] || (seen[x][y] && seen[i][j] - seen[x][y] < 3)) continue;
            if (seen[x][y] && seen[i][j] - seen[x][y] >= 3) return true;
            if (dfs(G, x, y, len + 1)) return true;
        }
        return false;
    }
public:
    bool containsCycle(vector<vector<char>>& G) {
        M = G.size(), N = G[0].size();
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (seen[i][j]) continue;
                if (dfs(G, i, j)) return true;
            }
        }
        return false;
    }
};

Solution 2. DFS

// OJ: https://leetcode.com/problems/detect-cycles-in-2d-grid/
// Time: O(MN)
// Space: O(MN)
class Solution {
    int seen[501][501] = {}, M, N, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
    bool dfs(vector<vector<char>> &G, int i, int j, int prevX, int prevY) {
        if (seen[i][j]) return true;
        seen[i][j] = 1;
        for (auto &[dx, dy] : dirs) {
            int x = i + dx, y = j + dy;
            if (x < 0 || x >= M || y < 0 || y >= N || G[x][y] != G[i][j] || (prevX == x && prevY == y)) continue;
            if (dfs(G, x, y, i, j)) return true;
        }
        return false;
    }
public:
    bool containsCycle(vector<vector<char>>& G) {
        M = G.size(), N = G[0].size();
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (seen[i][j]) continue;
                if (dfs(G, i, j, -1, -1)) return true;
            }
        }
        return false;
    }
};
  • class Solution {
        int rows;
        int columns;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        boolean flag = false;
    
        public boolean containsCycle(char[][] grid) {
            rows = grid.length;
            columns = grid[0].length;
            if (rows < 2 || columns < 2)
                return false;
            boolean[][] visited = new boolean[rows][columns];
            for (int i = 0; i < rows && !flag; i++) {
                for (int j = 0; j < columns && !flag; j++) {
                    if (!visited[i][j])
                        depthFirstSearch(grid, visited, i, j);
                }
            }
            return flag;
        }
    
        public void depthFirstSearch(char[][] grid, boolean[][] visited, int row, int column) {
            visited[row][column] = true;
            char c = grid[row][column];
            int value = row * columns + column;
            for (int[] direction : directions) {
                int newRow = row + direction[0], newColumn = column + direction[1];
                if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && grid[newRow][newColumn] == c) {
                    int key = newRow * columns + newColumn;
                    if (!visited[newRow][newColumn]) {
                        map.put(key, value);
                        depthFirstSearch(grid, visited, newRow, newColumn);
                    } else if (map.getOrDefault(value, -1) != key)
                        flag = true;
                }
            }
        }
    }
    
    ############
    
    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];
        }
    }
    
  • // OJ: https://leetcode.com/problems/detect-cycles-in-2d-grid/
    // Time: O(MN)
    // Space: O(MN)
    class Solution {
        int seen[501][501] = {}, M, N, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
        bool dfs(vector<vector<char>> &G, int i, int j, int len = 1) {
            seen[i][j] = len;
            for (auto &[dx, dy] : dirs) {
                int x = i + dx, y = j + dy;
                if (x < 0 || x >= M || y < 0 || y >= N || G[x][y] != G[i][j] || (seen[x][y] && seen[i][j] - seen[x][y] < 3)) continue;
                if (seen[x][y] && seen[i][j] - seen[x][y] >= 3) return true;
                if (dfs(G, x, y, len + 1)) return true;
            }
            return false;
        }
    public:
        bool containsCycle(vector<vector<char>>& G) {
            M = G.size(), N = G[0].size();
            for (int i = 0; i < M; ++i) {
                for (int j = 0; j < N; ++j) {
                    if (seen[i][j]) continue;
                    if (dfs(G, i, j)) return true;
                }
            }
            return false;
        }
    };
    
  • class Solution:
        def containsCycle(self, grid: List[List[str]]) -> bool:
            def find(x):
                if p[x] != x:
                    p[x] = find(p[x])
                return p[x]
    
            m, n = len(grid), len(grid[0])
            p = list(range(m * n))
            for i in range(m):
                for j in range(n):
                    for a, b in [[0, 1], [1, 0]]:
                        x, y = i + a, j + b
                        if x < m and y < n and grid[x][y] == grid[i][j]:
                            if find(x * n + y) == find(i * n + j):
                                return True
                            p[find(x * n + y)] = find(i * n + j)
            return False
    
    
    
  • func containsCycle(grid [][]byte) bool {
    	m, n := len(grid), len(grid[0])
    	p := make([]int, m*n)
    	for i := range p {
    		p[i] = i
    	}
    	var find func(x int) int
    	find = func(x int) int {
    		if p[x] != x {
    			p[x] = find(p[x])
    		}
    		return p[x]
    	}
    	dirs := []int{1, 0, 1}
    	for i := 0; i < m; i++ {
    		for j := 0; j < n; j++ {
    			for k := 0; k < 2; k++ {
    				x, y := i+dirs[k], j+dirs[k+1]
    				if x < m && y < n && grid[x][y] == grid[i][j] {
    					if find(x*n+y) == find(i*n+j) {
    						return true
    					}
    					p[find(x*n+y)] = find(i*n + j)
    				}
    			}
    		}
    	}
    	return false
    }
    
  • /**
     * @param {character[][]} grid
     * @return {boolean}
     */
    var containsCycle = function (grid) {
        const m = grid.length;
        const n = grid[0].length;
        let p = Array.from({ length: m * n }, (_, i) => i);
        function find(x) {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        }
        const dirs = [0, 1, 0];
        for (let i = 0; i < m; ++i) {
            for (let j = 0; j < n; ++j) {
                for (let k = 0; k < 2; ++k) {
                    const x = i + dirs[k];
                    const y = j + dirs[k + 1];
                    if (x < m && y < n && grid[x][y] == grid[i][j]) {
                        if (find(x * n + y) == find(i * n + j)) {
                            return true;
                        }
                        p[find(x * n + y)] = find(i * n + j);
                    }
                }
            }
        }
        return false;
    };
    
    

All Problems

All Solutions