Watch 10 video solutions for Regions Cut By Slashes, a medium level problem involving Array, Hash Table, Depth-First Search. This walkthrough by NeetCodeIO has 20,373 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Given the grid grid represented as a string array, return the number of regions.
Note that backslash characters are escaped, so a '\' is represented as '\\'.
Example 1:
Input: grid = [" /","/ "] Output: 2
Example 2:
Input: grid = [" /"," "] Output: 1
Example 3:
Input: grid = ["/\\","\\/"] Output: 5 Explanation: Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.
Constraints:
n == grid.length == grid[i].length1 <= n <= 30grid[i][j] is either '/', '\', or ' '.Problem Overview: You get an n x n grid where each cell contains '/', '\', or a blank space. These slashes divide the grid into multiple regions. The goal is to count how many disconnected regions are formed after all divisions.
Approach 1: Represent Each Grid Cell by a Subdivision into Smaller Triangles (DFS/BFS) (Time: O(n^2), Space: O(n^2))
Each grid cell can be split into four small triangles. A slash determines which triangles connect internally. For example, '/' connects the top-left and bottom-right boundaries differently than '\'. After subdivision, treat every triangle as a node in a graph. Use depth-first search or breadth-first search to explore connected triangles. Whenever you start a DFS from an unvisited triangle, you’ve discovered a new region. The grid effectively becomes 4 * n * n nodes, but traversal is still linear relative to the expanded graph.
This approach is intuitive because it converts the geometric problem into a standard graph traversal problem. If you’re comfortable with grid DFS problems, this method is straightforward to implement and easy to reason about.
Approach 2: Union-Find to Track Regions (Time: O(n^2 α(n)), Space: O(n^2))
Another way to model the grid is by splitting each cell into four subregions and connecting them using a Union-Find (Disjoint Set Union) structure. Inside each cell, union operations depend on the slash type. For example, a blank cell connects all four triangles, while '/' and '\' connect specific pairs. You also union triangles between neighboring cells so adjacent edges share the same component.
After processing the entire matrix, the number of unique DSU parents represents the number of regions. Path compression and union by rank keep operations nearly constant time. This approach avoids explicit graph traversal and works well when you prefer a connectivity model.
Recommended for interviews: The Union-Find solution is typically what interviewers expect because it demonstrates strong understanding of connected components and disjoint-set structures. The triangle subdivision with DFS shows good problem decomposition and is easier to visualize, but the DSU approach highlights algorithmic maturity and clean region counting.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Grid Subdivision with DFS/BFS | O(n^2) | O(n^2) | When you want a clear graph traversal model and easier visualization of regions |
| Union-Find (Disjoint Set Union) | O(n^2 α(n)) | O(n^2) | Preferred in interviews when solving connected component problems efficiently |