Log inSign up
mediumLeetCodeNot Started

Regions Cut By Slashes

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

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 of size n, return the *number of regions*.

Note that backslash characters are represented as '' in code.

Constraints:

  • n == grid.length == grid[i].length
  • 1 <= n <= 30
  • grid[i][j] is either /, \, or ' '.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Transform diagonal line partition problems into grid flood fill via resolution upscaling.
  • Understand why 3 × 3 scaling is required over 2 × 2 to preserve 4-directional boundary isolation.
  • Implement flood fill (DFS/BFS) on transformed matrices.
  • Understand the alternative 4-triangle Disjoint Set Union (DSU) topological model.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever geometric partitions or diagonal cuts split continuous 2D space, upscale each cell into a higher-resolution subgrid (3 × 3) to convert diagonal line segments into solid orthogonally blocking walls. Once upscaled, standard flood fill directly counts topological regions.

1. DFS Flood Fill on 3x3 Upscaled Grid

Intuition

Expand the n × n grid into a (3n) × (3n) binary matrix initialized to 0. For each character: - '/': set (r*3+0, c*3+2), (r*3+1, c*3+1), (r*3+2, c*3+0) to 1. - '': set (r*3+0, c*3+0), (r*3+1, c*3+1), (r*3+2, c*3+2) to 1. Then run standard DFS flood fill over the (3n) × (3n) grid to count connected components of 0s.

Algorithm

  1. Let N = grid.length. Create a 3N × 3N matrix g filled with 0.
  2. For each cell (r, c) in grid:
  3. If grid[r][c] == '/':
  4. g[r*3][c*3 + 2] = 1, g[r*3 + 1][c*3 + 1] = 1, g[r*3 + 2][c*3] = 1
  5. Else if grid[r][c] == '\' :
  6. g[r*3][c*3] = 1, g[r*3 + 1][c*3 + 1] = 1, g[r*3 + 2][c*3 + 2] = 1
  7. Initialize regions = 0.
  8. For each cell (i, j) in 3N × 3N:
  9. If g[i][j] == 0:
  10. regions++
  11. Run dfs(i, j) to mark all 4-directionally reachable 0s as 1 (visited).
  12. Return regions.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5void dfs(int r, int c, std::vector<std::vector<int>>& g, int size) {
6 if (r < 0 || r >= size || c < 0 || c >= size || g[r][c] != 0) return;
7 g[r][c] = 1;
8 dfs(r - 1, c, g, size);
9 dfs(r + 1, c, g, size);
10 dfs(r, c - 1, g, size);
11 dfs(r, c + 1, g, size);
12}
13
14int regionsBySlashesDFS(std::vector<std::string>& grid) {
15 int n = grid.size();
16 int size = 3 * n;
17 std::vector<std::vector<int>> g(size, std::vector<int>(size, 0));
18
19 for (int r = 0; r < n; ++r) {
20 for (int c = 0; c < n; ++c) {
21 if (grid[r][c] == '/') {
22 g[r * 3][c * 3 + 2] = 1;
23 g[r * 3 + 1][c * 3 + 1] = 1;
24 g[r * 3 + 2][c * 3] = 1;
25 } else if (grid[r][c] == '\\') {
26 g[r * 3][c * 3] = 1;
27 g[r * 3 + 1][c * 3 + 1] = 1;
28 g[r * 3 + 2][c * 3 + 2] = 1;
29 }
30 }
31 }
32
33 int regions = 0;
34 for (int i = 0; i < size; ++i) {
35 for (int j = 0; j < size; ++j) {
36 if (g[i][j] == 0) {
37 regions++;
38 dfs(i, j, g, size);
39 }
40 }
41 }
42 return regions;
43}
44
45int main() {
46 std::vector<std::string> grid = {" /", "/ "};
47 std::cout << "Regions (DFS): " << regionsBySlashesDFS(grid) << std::endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(N^2) where N is grid.length. The upscaled grid has (3N)^2 = 9N^2 cells. For N = 30, 9*900 = 8100 cells, extremely fast.
  • Space complexity: O(N^2) to store the 3N x 3N grid and recursion stack.

2. BFS Flood Fill on 3x3 Upscaled Grid

Intuition

Instead of recursive DFS which can cause call-stack overflow on deep paths, use an iterative Queue-based BFS to flood fill open cells on the 3N × 3N upscaled grid.

Algorithm

  1. Construct 3N × 3N binary grid g with slashes represented as 1s.
  2. Initialize regions = 0.
  3. For each cell (i, j) in 3N × 3N:
  4. If g[i][j] == 0:
  5. regions++
  6. Initialize queue, push (i, j), set g[i][j] = 1.
  7. While queue is not empty:
  8. Pop (r, c), explore 4 neighbors (nr, nc).
  9. If in bounds and g[nr][nc] == 0, set g[nr][nc] = 1 and push to queue.
  10. Return regions.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <queue>
5
6int regionsBySlashesBFS(std::vector<std::string>& grid) {
7 int n = grid.size();
8 int size = 3 * n;
9 std::vector<std::vector<int>> g(size, std::vector<int>(size, 0));
10
11 for (int r = 0; r < n; ++r) {
12 for (int c = 0; c < n; ++c) {
13 if (grid[r][c] == '/') {
14 g[r * 3][c * 3 + 2] = 1;
15 g[r * 3 + 1][c * 3 + 1] = 1;
16 g[r * 3 + 2][c * 3] = 1;
17 } else if (grid[r][c] == '\\') {
18 g[r * 3][c * 3] = 1;
19 g[r * 3 + 1][c * 3 + 1] = 1;
20 g[r * 3 + 2][c * 3 + 2] = 1;
21 }
22 }
23 }
24
25 int regions = 0;
26 int dr[] = {-1, 1, 0, 0};
27 int dc[] = {0, 0, -1, 1};
28
29 for (int i = 0; i < size; ++i) {
30 for (int j = 0; j < size; ++j) {
31 if (g[i][j] == 0) {
32 regions++;
33 std::queue<std::pair<int, int>> q;
34 q.push({i, j});
35 g[i][j] = 1;
36
37 while (!q.empty()) {
38 auto [r, c] = q.front();
39 q.pop();
40
41 for (int d = 0; d < 4; ++d) {
42 int nr = r + dr[d], nc = c + dc[d];
43 if (nr >= 0 && nr < size && nc >= 0 && nc < size && g[nr][nc] == 0) {
44 g[nr][nc] = 1;
45 q.push({nr, nc});
46 }
47 }
48 }
49 }
50 }
51 }
52 return regions;
53}
54
55int main() {
56 std::vector<std::string> grid = {"/\\", "\\/"};
57 std::cout << "Regions (BFS): " << regionsBySlashesBFS(grid) << std::endl;
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(N^2) where N is grid.length. Visits each of the 9N^2 cells once.
  • Space complexity: O(N^2) for the upscaled grid and BFS queue.

3. Disjoint Set Union (4 Triangles per Cell)

Intuition

Divide each 1 × 1 square into 4 triangles numbered 0 (North), 1 (East), 2 (South), 3 (West). For N × N squares, there are 4N2 triangles in total. Within each cell, connect triangles based on slashes: - Space ' ': union all 4 triangles (0-1-2-3). - Slash '/': union 0 with 3, and 1 with 2. - Backslash '': union 0 with 1, and 2 with 3. Then connect adjacent cells: connect South triangle of (r, c) with North triangle of (r+1, c), and East triangle of (r, c) with West triangle of (r, c+1). Return the number of disjoint components.

Algorithm

  1. Initialize DSU with 4 × n × n elements, components = 4n2.
  2. For each cell (r, c) with base index root = 4 * (r * n + c):
  3. Index 0: North, 1: East, 2: South, 3: West.
  4. Internal connections:
  5. If grid[r][c] == '/':
  6. union(root + 0, root + 3), union(root + 1, root + 2)
  7. Else if grid[r][c] == '\' :
  8. union(root + 0, root + 1), union(root + 2, root + 3)
  9. Else (space):
  10. union(root + 0, root + 1), union(root + 1, root + 2), union(root + 2, root + 3)
  11. Adjacent connections:
  12. If r + 1 < n: union(root + 2, 4 * ((r + 1) * n + c) + 0) [South to North]
  13. If c + 1 < n: union(root + 1, 4 * (r * n + (c + 1)) + 3) [East to West]
  14. Return dsu.components.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <numeric>
5
6class DSU {
7 std::vector<int> parent;
8 int count;
9public:
10 DSU(int n) : parent(n), count(n) {
11 std::iota(parent.begin(), parent.end(), 0);
12 }
13 int find(int i) {
14 if (parent[i] == i) return i;
15 return parent[i] = find(parent[i]);
16 }
17 void unite(int i, int j) {
18 int rootI = find(i);
19 int rootJ = find(j);
20 if (rootI != rootJ) {
21 parent[rootI] = rootJ;
22 count--;
23 }
24 }
25 int getCount() const { return count; }
26};
27
28int regionsBySlashes(std::vector<std::string>& grid) {
29 int n = grid.size();
30 DSU dsu(4 * n * n);
31
32 for (int r = 0; r < n; ++r) {
33 for (int c = 0; c < n; ++c) {
34 int root = 4 * (r * n + c);
35 char val = grid[r][c];
36
37 // Internal cell unions
38 if (val == '/') {
39 dsu.unite(root + 0, root + 3);
40 dsu.unite(root + 1, root + 2);
41 } else if (val == '\\') {
42 dsu.unite(root + 0, root + 1);
43 dsu.unite(root + 2, root + 3);
44 } else {
45 dsu.unite(root + 0, root + 1);
46 dsu.unite(root + 1, root + 2);
47 dsu.unite(root + 2, root + 3);
48 }
49
50 // Neighbor connections
51 if (r + 1 < n) {
52 dsu.unite(root + 2, 4 * ((r + 1) * n + c) + 0); // South to North
53 }
54 if (c + 1 < n) {
55 dsu.unite(root + 1, 4 * (r * n + (c + 1)) + 3); // East to West
56 }
57 }
58 }
59 return dsu.getCount();
60}
61
62int main() {
63 std::vector<std::string> grid = {" /", "/ "};
64 std::cout << "Optimal Regions (DSU): " << regionsBySlashes(grid) << std::endl;
65 return 0;
66}

Time & Space Complexity

  • Time complexity: O(N^2 * alpha(N)) where N is grid.length. Exactly 4N^2 items with constant number of unions per cell.
  • Space complexity: O(N^2) for the DSU parent and rank arrays of size 4N^2.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.3x3 Upscale + DFS Flood FillO(N^2)O(N^2)Very intuitive; converts complex geometric cuts into standard 2D grid flood fill.Allocates 9N2 grid memory and uses recursion.
2.3x3 Upscale + BFS Flood FillO(N^2)O(N^2)Prevents call stack depth overflow by using a standard FIFO queue.Still creates 9N2 upscaled matrix.
3.4-Triangle Disjoint Set Union (DSU)OptimalO(N^2 * alpha(N))O(N^2)Pure topological formulation; connects 4 triangles per cell with zero resolution expansion artifacts; uses only 4N2 items.Requires careful triangle indexing and neighbor boundary unions.

Common Pitfalls & Crucial Edge Cases

Using 2x2 upscaling instead of 3x3 upscaling.

2x2 upscaling fails on diagonal corner touching; always use 3x3 upscaling for diagonal cuts.

Forgetting to escape the backslash character in conditional checks (grid[r][c] == '\\').

A single backslash escapes the next character; write \ to match a literal backslash.

Crucial Edge Cases to Validate:

  • Entire grid consists of spaces ' ' — No slashes present; returns 1 single open region.
  • n = 1 — A single 1x1 square with / or \ splits the square into 2 regions; algorithm returns 2.
  • Grid forms closed cycles / polygon pockets (e.g. ['/\\', '\\/']) — Creates an enclosed center diamond region and 4 outer regions, correctly returning 5.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention both the 3x3 upscaling trick and the 4-triangle DSU approach. Interviewers love the geometric intuition of 3x3 upscaling!
  2. Clearly explain why 2x2 fails: 'Diagonal lines touch only at corner vertices, which causes diagonal leakage in standard 4-way flood fill.'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does a 2x2 upscaling fail while a 3x3 upscaling succeeds?

2.In the 4-triangle DSU approach, how many total triangles are modeled for an N x N grid?

3.How are backslashes represented in source string arrays in C++, Java, and Python?

Back to DSA Sheet