Detect Cycles in 2D Grid

Given a 2D character grid, determine whether there exists a cycle formed by equal characters using 4-directional adjacency. DSU can be used to connect same-character cells and detect when a new union attempts to join cells already in the same set.

Input Format

grid = character matrix

Output Format

whether a cycle exists among equal characters

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]

Output:

true

Explanation:

The 'a' cells on the border form a cycle.

Example 2:

Input:

grid = [["a","b"],["c","d"]]

Output:

false

Explanation:

No two equal adjacent cells exist, so no cycle can form.

Example 3:

Input:

grid = [["a","a"],["a","a"]]

Output:

true

Explanation:

A 2x2 block of the same character forms a cycle.

Loading...
Detect Cycles in 2D Grid - Union Find