Leetcode 1559: Detect Cycles in 2D Grid
Given a 2D grid of characters, find if there exists a cycle where the same character repeats in the grid. A cycle is defined as a path where a character appears 4 or more times, forming a loop that starts and ends at the same cell. The cycle must consist of adjacent cells, and you are not allowed to revisit the previous cell.
Problem
Approach
Steps
Complexity
Input: The input consists of a 2D array of characters representing the grid, where the size of the grid is m x n. The grid only contains lowercase English letters.
Example: Input: grid = [['a', 'b', 'a'], ['b', 'a', 'b'], ['a', 'b', 'a']]
Constraints:
• 1 <= m, n <= 500
• grid consists only of lowercase English letters
Output: Return true if there is a cycle of the same character in the grid, otherwise return false.
Example: Output: true
Constraints:
Goal: We need to identify if there exists a cycle in the grid where a character repeats in a loop of 4 or more cells.
Steps:
• Iterate through all cells in the grid.
• For each unvisited cell, perform a depth-first search (DFS) to find a cycle of the same character.
• Keep track of the previous cell to avoid revisiting it in the next step.
• If a cycle is found, return true, else continue to the next cell.
• Return false if no cycle is found.
Goal: The grid is a 2D array with a size of m x n, where both m and n are between 1 and 500. All cells contain lowercase letters.
Steps:
• 1 <= m, n <= 500
• grid consists only of lowercase English letters
Assumptions:
• A cycle must consist of at least 4 cells.
• The cycle must only consist of adjacent cells in one of four directions (up, down, left, right).
• Input: Example 1: grid = [['a', 'a', 'a', 'a'], ['a', 'b', 'b', 'a'], ['a', 'b', 'b', 'a'], ['a', 'a', 'a', 'a']]
• Explanation: There are two valid cycles in the grid: one cycle in the top-left corner and another one in the bottom-right corner.
• Input: Example 2: grid = [['a', 'b', 'a'], ['b', 'a', 'b'], ['a', 'b', 'a']]
• Explanation: There is no valid cycle in this grid as the characters don't form a loop of length 4 or more.
Approach: The problem can be solved using depth-first search (DFS) to detect cycles in the grid. During the DFS, we keep track of the path to ensure we don't revisit the last cell in the cycle.
Observations:
• The grid can have up to 500 x 500 cells, so an efficient search is needed.
• The DFS will be used to explore each unvisited cell and check for cycles.
• A DFS approach ensures we can explore all possible cycles starting from each cell.
Steps:
• Create a visited array to track which cells have been visited.
• For each cell, if it is unvisited, start a DFS to explore all possible cycles.
• During DFS, ensure the previous cell is not revisited, and check if the current path forms a cycle.
Empty Inputs:
• An empty grid would return false since there are no cells to form a cycle.
Large Inputs:
• For large grids (500 x 500), ensure the DFS is optimized to prevent time limit exceeded errors.
Special Values:
• A grid with only one character may form a valid cycle if the path length is sufficient.
Constraints:
• Ensure that the grid size does not exceed the maximum constraints.
bool containsCycle(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<bool>> vis(m, vector<bool>(n, false));
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(!vis[i][j] && dfs(grid, vis, i, j, -1, -1, grid[i][j])) return true;
return false;
}
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool dfs(vector<vector<char>> &grid, vector<vector<bool>> &vis, int i, int j, int pi, int pj, char node) {
if(vis[i][j]) return true;
vis[i][j] = true;
for(auto d: dir) {
int ni = i + d[0];
int nj = j + d[1];
if(min(ni, nj) < 0 ||
ni > grid.size() - 1 ||
nj > grid[0].size() - 1 ||
grid[ni][nj] != node)
continue;
if((ni == pi) && (nj == pj)) continue;
if(dfs(grid, vis, ni, nj, i, j, node))
return true;
}
return false;
}
1 : Function Declaration
bool containsCycle(vector<vector<char>>& grid) {
This is the function definition for `containsCycle`. It takes a 2D grid of characters (`grid`) and checks if there exists a cycle in the grid. The function returns a boolean value indicating whether a cycle is detected.
2 : Variable Initialization
int m = grid.size(), n = grid[0].size();
This line calculates the number of rows `m` and columns `n` of the grid.
3 : Variable Initialization
vector<vector<bool>> vis(m, vector<bool>(n, false));
This line initializes a 2D vector `vis` of size `m x n` to track visited cells. All elements are initially set to `false`.
4 : Loop Iteration
for(int i = 0; i < m; i++)
The outer for loop iterates through all rows in the grid, represented by the variable `i`.
5 : Loop Iteration
for(int j = 0; j < n; j++)
The inner for loop iterates through all columns in the current row, represented by the variable `j`.
6 : Condition Check
if(!vis[i][j] && dfs(grid, vis, i, j, -1, -1, grid[i][j])) return true;
If the current cell has not been visited and a cycle is detected using DFS starting from that cell, the function immediately returns `true`.
7 : Return Statement
return false;
If no cycle is found in the grid after traversing all cells, the function returns `false`.
8 : Global Variable
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
This line defines a global variable `dir` that holds the possible movement directions (right, left, down, up) for DFS traversal in the grid.
9 : Function Declaration
bool dfs(vector<vector<char>> &grid, vector<vector<bool>> &vis, int i, int j, int pi, int pj, char node) {
This is the DFS function declaration. It checks for cycles by recursively visiting neighboring cells and marking cells as visited.
10 : Condition Check
if(vis[i][j]) return true;
If the current cell has already been visited, it means a cycle has been detected, so the function returns `true`.
11 : Mark Visited
vis[i][j] = true;
The current cell is marked as visited in the `vis` array to avoid revisiting it in future iterations.
12 : Loop Iteration
for(auto d: dir) {
This loop iterates over each of the four possible movement directions (right, left, down, up) defined in `dir`.
13 : Variable Update
int ni = i + d[0];
This calculates the new row index `ni` based on the current direction `d[0]`.
14 : Variable Update
int nj = j + d[1];
This calculates the new column index `nj` based on the current direction `d[1]`.
15 : Bounds Check
if(min(ni, nj) < 0 || ni > grid.size() - 1 || nj > grid[0].size() - 1 || grid[ni][nj] != node)
This checks if the new position `(ni, nj)` is out of bounds or if the character in the grid at that position does not match the current node.
16 : Skip Invalid Move
continue;
If the new position is invalid or does not match the current node, the loop continues to the next direction.
17 : Skip Parent
if((ni == pi) && (nj == pj)) continue;
If the new position is the parent of the current cell (i.e., the cell from which the current DFS call originated), the loop continues to avoid revisiting the parent.
18 : Recursive Call
if(dfs(grid, vis, ni, nj, i, j, node))
If the DFS call to the neighboring cell returns `true`, it indicates that a cycle has been found, so `true` is returned.
19 : Return Statement
return false;
If no cycle is found during the DFS, `false` is returned.
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: In the worst case, we visit every cell and perform a DFS from each unvisited cell.
Best Case: O(m * n)
Worst Case: O(m * n)
Description: The space complexity is proportional to the size of the grid due to the visited array and the DFS stack.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus