959. Regions Cut By Slashes

How to solve Regions Cut By Slashes (LeetCode 959): the approach in brief

The problem

An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a '/', '\', or blank space ' '. These characters divide the square into contiguous regions.

Pattern

Regions Cut By Slashes is a Graph Traversal Patterns (DFS & BFS) problem, in the Union-Find (Disjoint Set Union - DSU) subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Master Union-Find data structure with path compression and union by rank for connectivity problems.

Approach outline

1. Think about representing each small square in the grid as multiple parts or nodes to better capture the divisions created by slashes.
2. Consider modeling the problem as a graph where these parts are nodes, and edges represent connectivity between them within and across squares.
3. Use a graph traversal algorithm like DFS or BFS to explore connected regions, counting distinct connected components as separate regions.

Complexity

The reference solution runs in O(N^2) time and O(N^2) space.

Asked at

Regions Cut By Slashes has been reported in interviews at Uber.