Regions Cut By Slashes

Regions Cut By Slashes

What is this problem about?

The Regions Cut By Slashes problem gives you an n×n grid of '/', '', and ' ' characters. Slashes divide cells into triangular regions. Count the total number of distinct regions in the full grid. This medium coding problem uses grid expansion (each cell becomes a 3×3 or 4×4 subgrid) with DFS/Union-Find to count connected regions. The array, matrix, union find, BFS, hash table, and DFS interview pattern is the core.

Why is this asked in interviews?

Uber, Microsoft, Meta, Amazon, TikTok, Google, and Bloomberg ask this because it requires a creative transformation: expand each cell to a 3×3 grid to model the diagonal cuts, then apply standard connected-components counting.

Algorithmic pattern used

Grid expansion + BFS/DFS flood fill. Expand each original cell to a 3×3 subgrid. For '/', mark the anti-diagonal pixels (1 blocked). For '', mark the main diagonal (1 blocked). For ' ', all 9 pixels free. Then count connected regions of free (0) pixels using BFS/DFS. Each connected component = one region.

Example explanation

Grid=[["/"]]. Expand 1×1 to 3×3:

010
100
000 (but '/' diagonal)

Actually /: mark cells (0,2),(1,1),(2,0). Two disconnected free regions in top-right and bottom-left. Regions = 2.

Common mistakes candidates make

• Not expanding cells (trying to work directly with '/', '' positions).
• Wrong diagonal marking (/ is anti-diagonal, \ is main diagonal).
• Off-by-one in expanded grid size.
• Not marking all three diagonal cells per character.

Interview preparation tip

Regions Cut By Slashes demonstrates grid transformation to simplify topology. By expanding to 3×3 per cell, continuous diagonal cuts become discrete blocked pixels, making standard flood fill applicable. Practice similar "grid transformation" problems where the original representation is too coarse for direct algorithm application. The expansion factor (3×3) preserves the connectivity structure faithfully.