1559. Detect Cycles in 2D Grid LeetCode Solution

In this guide, you will get 1559. Detect Cycles in 2D Grid LeetCode Solution with the best time and space complexity. The solution to Detect Cycles in D Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Detect Cycles in D Grid solution in C++
Detect Cycles in D Grid solution in Java
Detect Cycles in D Grid solution in Python
Additional Resources

1559. Detect Cycles in 2D Grid LeetCode Solution image

Problem Statement of Detect Cycles in D Grid

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.
Also, you cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.
Return true if any cycle of the same value exists in grid, otherwise, return false.

Example 1:

Input: grid = [[“a”,”a”,”a”,”a”],[“a”,”b”,”b”,”a”],[“a”,”b”,”b”,”a”],[“a”,”a”,”a”,”a”]]
Output: true
Explanation: There are two valid cycles shown in different colors in the image below:

Example 2:

Input: grid = [[“c”,”c”,”c”,”a”],[“c”,”d”,”c”,”c”],[“c”,”c”,”e”,”c”],[“f”,”c”,”c”,”c”]]
Output: true
Explanation: There is only one valid cycle highlighted in the image below:

Example 3:

Input: grid = [[“a”,”b”,”b”],[“b”,”z”,”b”],[“b”,”b”,”a”]]
Output: false

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid consists only of lowercase English letters.

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

1559. Detect Cycles in 2D Grid LeetCode Solution in C++

class Solution {
 public:
  bool containsCycle(vector<vector<char>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    vector<vector<bool>> seen(m, vector<bool>(n));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        if (seen[i][j])
          continue;
        if (dfs(grid, i, j, -1, -1, grid[i][j], seen))
          return true;
      }

    return false;
  }

 private:
  static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  bool dfs(const vector<vector<char>>& grid, int i, int j, int prevI, int prevJ,
           char c, vector<vector<bool>>& seen) {
    seen[i][j] = true;

    for (const auto& [dx, dy] : dirs) {
      const int x = i + dx;
      const int y = j + dy;
      if (x < 0 || x == grid.size() || y < 0 || y == grid[0].size())
        continue;
      if (x == prevI && y == prevJ)
        continue;
      if (grid[x][y] != c)
        continue;
      if (seen[x][y])
        return true;
      if (dfs(grid, x, y, i, j, c, seen))
        return true;
    }

    return false;
  }
};
/* code provided by PROGIEZ */

1559. Detect Cycles in 2D Grid LeetCode Solution in Java

class Solution {
  public boolean containsCycle(char[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    boolean[][] seen = new boolean[m][n];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        if (seen[i][j])
          continue;
        if (dfs(grid, i, j, -1, -1, grid[i][j], seen))
          return true;
      }

    return false;
  }

  private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  private boolean dfs(char[][] grid, int i, int j, int prevI, int prevJ, char c, boolean[][] seen) {
    seen[i][j] = true;

    for (int[] dir : dirs) {
      final int x = i + dir[0];
      final int y = j + dir[1];
      if (x < 0 || x == grid.length || y < 0 || y == grid[0].length)
        continue;
      if (x == prevI && y == prevJ)
        continue;
      if (grid[x][y] != c)
        continue;
      if (seen[x][y])
        return true;
      if (dfs(grid, x, y, i, j, c, seen))
        return true;
    }

    return false;
  }
}
// code provided by PROGIEZ