Solution
Approach 1: UnionFind
Intuition
To find the number of components in a graph, we can use either depthfirst search or union find. The main difficulty with this problem is in specifying the graph.
One "brute force" way to specify the graph is to associate each grid square with 4 nodes (north, south, west, and east), representing 4 triangles inside the square if it were to have both slashes. Then, we can connect all 4 nodes if the grid square is " "
, and connect two pairs if the grid square is "/"
or "\"
. Finally, we can connect all neighboring nodes (for example, the east node of the square at grid[0][0]
connects with the west node of the square at grid[0][1]
).
This is the most straightforward approach, but there are other approaches that use less nodes to represent the underlying information.
Algorithm
Create 4*N*N
nodes, one for each grid square, and connect them as described above. After, we use a union find structure to find the number of connected components.
We will skip the explanation of how a DSU structure is implemented. Please refer to https://leetcode.com/problems/redundantconnection/solution/ for a tutorial on DSU.
Complexity Analysis

Time Complexity: , where is the length of the grid, and is the InverseAckermann function (if we were to use unionfind by rank.)

Space Complexity: .