Leetcode.com problem 1559: "Detect Cycles in 2D Grid"

James S. Plank

Mon Apr 27 10:34:16 EDT 2026

Problem Statement.
Success Rate (as of July, 2022): 63.1%
This is a "medium" problem
I don't have offline material for this, so use Leetcode to test your code.

This is about as straightforward of a cycle detection problem as you can get. You can solve it with a DFS, where you make sure to include the id of the calling node, so that you don't traverse an edge back to your caller, because that doesn't make a cycle. This is the exact same way that we did cycle detection in the CS302 lecture notes.

I suggest adding the following to the Solution class:

A copy of the grid.
A "visited" grid that is the same size as the grid. I made this a vector of strings, where each element starts at '0'. I used the character 'a' to denote that a node is involved in cycle detection, and 'b' to denote that we processed the node, and it wasn't part of a cycle.

A DFS method that is something like:

bool DFS(int r, int c, int from_r, int from_c);

Give it a try, but if you want more help, keep reading:

Here's the pseudo-code of the DFS:

bool DFS(int r, int c, int from_r, int from_c)
{
  if (V[r][c] shows that we're in the DFS already from r and c, return true, because we just detected a cycle.
  if (V[r][c] shows that we've already processed r and c, return false.
  set V[r][c] to show that we're in the DFS from r and c
  for each of the four legal directions from r and c:
    if (there is a node in that direction, and
        that node's character matches the character in r and c, and
        that node is not (from_r,from_c)) then
      do the DFS to that node.
        If it returns true, we're done and we found a cycle -- return true.
        If it returns false, keep going.
  If we get here, then there is no cycle involving r and c, so:
    set V[r][c] to show that we already processed r and c
    return false
}

It's good practice for you to write this.

If you read the problem editorial, you'll see that you can also solve this with disjoint sets, and it's faster. That's all well and good, but I think it's good practice for you to write the DFS.