Regions Cut By Slashes

Med

#0913Time: O(N^2). Building the `3N x 3N` grid takes O(N^2) time. The subsequent DFS/BFS traversal also takes O((3N)^2) = O(N^2) time as each cell in the upscaled grid is visited at most once.Space: O(N^2), where N is the side length of the input grid. This is for storing the `3N x 3N` upscaled grid and for the recursion stack depth in the worst case.

Algorithms

Depth-First Search Breadth-First Search Union Find

Data structures

Array Hash Table Matrix

Prompt

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].length
1 <= n <= 30
grid[i][j] is either '/', '\', or ' '.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach solves the problem by transforming the input grid into a higher-resolution grid. Each 1x1 cell of the original grid is 'upscaled' to a 3x3 subgrid of pixels. The slashes ('/' and '\') are drawn as 'walls' or 'barriers' (e.g., represented by 0s) in these subgrids, while the rest of the space remains open (e.g., represented by 1s).

After this transformation, the problem is reduced to a standard 'number of islands' or 'connected components' problem on the new 3n x 3n grid. We can then traverse this grid using Depth-First Search (DFS) or Breadth-First Search (BFS) to count the number of contiguous areas of open space.

Algorithm

Create a new 3n x 3n integer grid, let's call it upscaledGrid, and initialize all its cells to 1, representing open space.
Iterate through the input n x n grid. For each cell grid[i][j]:
- If the character is '/', it forms a barrier from top-right to bottom-left. In the 3x3 subgrid corresponding to (i,j), set the pixels (3i, 3j+2), (3i+1, 3j+1), and (3i+2, 3j) to 0 (barrier).
- If the character is '\', it forms a barrier from top-left to bottom-right. Set the pixels (3i, 3j), (3i+1, 3j+1), and (3i+2, 3j+2) to 0.
- If the character is a space ' ', the 3x3 subgrid remains all 1s.
Initialize a counter regionCount to 0.
Iterate through every cell (r, c) of the 3n x 3n upscaledGrid.
If upscaledGrid[r][c] is 1 (an unvisited part of a region):
- Increment regionCount.
- Start a graph traversal (like Depth-First Search or Breadth-First Search) from (r, c).
- The traversal should visit all reachable cells with a value of 1 and mark them as visited (e.g., by changing their value to 0) to avoid recounting them.
After iterating through the entire upscaledGrid, regionCount will hold the total number of regions. Return regionCount.

Walkthrough

The core idea is to make the connections between regions explicit by using a finer grid. A 1x1 cell is not granular enough to represent the connections properly, but a 3x3 subgrid is. For example, a '/' in cell (i,j) divides it into two regions. In the 3x3 model, this is represented by a diagonal line of 0s, which separates two areas of 1s. These areas of 1s can then connect to adjacent 3x3 subgrids, correctly modeling how regions merge across cell boundaries.

Once the 3n x 3n grid is constructed, we iterate through it. Whenever we find a 1 that we haven't visited yet, we've discovered a new region. We increment our region counter and then use DFS to find and mark all parts of that same region, so we don't count it again. This process continues until the entire grid has been checked.

1class Solution {2    public int regionsBySlashes(String[] grid) {3        int n = grid.length;4        int[][] upscaledGrid = new int[3 * n][3 * n];5 6        for (int i = 0; i < n; i++) {7            for (int j = 0; j < n; j++) {8                char c = grid[i].charAt(j);9                if (c == '/') {10                    upscaledGrid[3 * i][3 * j + 2] = 1;11                    upscaledGrid[3 * i + 1][3 * j + 1] = 1;12                    upscaledGrid[3 * i + 2][3 * j] = 1;13                } else if (c == '\\') {14                    upscaledGrid[3 * i][3 * j] = 1;15                    upscaledGrid[3 * i + 1][3 * j + 1] = 1;16                    upscaledGrid[3 * i + 2][3 * j + 2] = 1;17                }18            }19        }20 21        int regions = 0;22        for (int i = 0; i < 3 * n; i++) {23            for (int j = 0; j < 3 * n; j++) {24                if (upscaledGrid[i][j] == 0) {25                    regions++;26                    dfs(upscaledGrid, i, j, 3 * n);27                }28            }29        }30        return regions;31    }32 33    private void dfs(int[][] grid, int r, int c, int size) {34        if (r < 0 || r >= size || c < 0 || c >= size || grid[r][c] == 1) {35            return;36        }37        grid[r][c] = 1; // Mark as visited38        dfs(grid, r + 1, c, size);39        dfs(grid, r - 1, c, size);40        dfs(grid, r, c + 1, size);41        dfs(grid, r, c - 1, size);42    }43}

Complexity

Time

O(N^2). Building the `3N x 3N` grid takes O(N^2) time. The subsequent DFS/BFS traversal also takes O((3N)^2) = O(N^2) time as each cell in the upscaled grid is visited at most once.

Space

O(N^2), where N is the side length of the input grid. This is for storing the `3N x 3N` upscaled grid and for the recursion stack depth in the worst case.

Trade-offs

Pros

The concept is highly intuitive and visual.
It transforms the problem into a well-known pattern (counting connected components), making it easier to implement for those familiar with it.

Cons

Requires more memory due to the 3n x 3n grid, leading to higher constant factors in space complexity.
The time complexity also has a higher constant factor (9n^2 vs 4n^2 operations) compared to the Union-Find approach.

A more efficient approach uses a Union-Find data structure. The main idea is to model the problem as finding the number of connected components among a set of small, fundamental regions. We can decompose each 1x1 cell into 4 triangular sub-regions (top, right, bottom, left).

We then use the Union-Find algorithm to group these sub-regions. Initially, each of the 4 * n * n sub-regions is in its own set. We iterate through the grid, and for each cell, we perform union operations. First, we unite the sub-regions within the cell based on the slash type. A space ' ' unites all 4 sub-regions, while '/' and '\' each create two pairs of united sub-regions. Second, we unite adjacent sub-regions across cell boundaries (e.g., the bottom of one cell with the top of the cell below it). The final number of disjoint sets remaining is the number of regions.

Algorithm

Divide each 1x1 cell of the grid into 4 smaller triangular sub-regions: 0 (top), 1 (right), 2 (bottom), and 3 (left).
This gives a total of 4 * n * n sub-regions. Initialize a Union-Find (or Disjoint Set Union - DSU) data structure for this many elements. The initial number of disjoint sets (regions) is 4 * n * n.
Map each sub-region k in cell (i, j) to a unique integer index, for example, (i * n + j) * 4 + k.
Iterate through each cell (i, j) of the input grid and perform union operations:
- Intra-cell unions: Based on the character in grid[i][j], merge the sub-regions within that cell.
  - If '/': Union the top (0) with left (3), and right (1) with bottom (2).
  - If '\': Union the top (0) with right (1), and bottom (2) with left (3).
  - If ' ': Union all four sub-regions together, e.g., union(0,1), union(1,2), union(2,3).
- Inter-cell unions: Merge sub-regions that are adjacent across cell boundaries.
  - If i < n-1, union the bottom sub-region (2) of cell (i, j) with the top sub-region (0) of cell (i+1, j).
  - If j < n-1, union the right sub-region (1) of cell (i, j) with the left sub-region (3) of cell (i, j+1).
Each time the union operation successfully merges two previously disconnected sets, the total count of regions decreases by one.
The final number of disjoint sets in the DSU structure is the answer.

Walkthrough

The Union-Find (DSU) data structure is perfectly suited for this problem because it efficiently tracks sets of connected elements. By breaking down each cell into 4 sub-regions, we create a consistent model for connections. The character in a cell ('/', '\', ' ') determines the internal connectivity, while the grid structure determines the external connectivity between cells.

The DSU is initialized with 4 * n * n elements, each representing a sub-region. The count of disjoint sets starts at 4 * n * n. As we iterate and perform union operations, this count decreases whenever two distinct regions are merged. After processing all intra-cell and inter-cell connections, the final count gives the number of contiguous regions in the entire grid.

1class Solution {2    class DSU {3        int[] parent;4        int count;5 6        public DSU(int n) {7            parent = new int[n];8            count = n;9            for (int i = 0; i < n; i++) {10                parent[i] = i;11            }12        }13 14        public int find(int i) {15            if (parent[i] == i) {16                return i;17            }18            return parent[i] = find(parent[i]);19        }20 21        public void union(int i, int j) {22            int rootI = find(i);23            int rootJ = find(j);24            if (rootI != rootJ) {25                parent[rootI] = rootJ;26                count--;27            }28        }29    }30 31    public int regionsBySlashes(String[] grid) {32        int n = grid.length;33        DSU dsu = new DSU(4 * n * n);34 35        for (int i = 0; i < n; i++) {36            for (int j = 0; j < n; j++) {37                int root = 4 * (i * n + j);38                // 0: top, 1: right, 2: bottom, 3: left39                char val = grid[i].charAt(j);40 41                // Intra-cell connections42                if (val == '/') {43                    dsu.union(root + 0, root + 3); // top-left44                    dsu.union(root + 1, root + 2); // right-bottom45                } else if (val == '\\') {46                    dsu.union(root + 0, root + 1); // top-right47                    dsu.union(root + 2, root + 3); // bottom-left48                } else { // ' '49                    dsu.union(root + 0, root + 1);50                    dsu.union(root + 1, root + 2);51                    dsu.union(root + 2, root + 3);52                }53 54                // Inter-cell connections55                // Connect to cell below56                if (i + 1 < n) {57                    int bottomRoot = 4 * ((i + 1) * n + j);58                    dsu.union(root + 2, bottomRoot + 0); // current bottom to next top59                }60                // Connect to cell to the right61                if (j + 1 < n) {62                    int rightRoot = 4 * (i * n + j + 1);63                    dsu.union(root + 1, rightRoot + 3); // current right to next left64                }65            }66        }67        return dsu.count;68    }69}

Complexity

Time

O(N^2 * α(N^2)), where α is the extremely slow-growing Inverse Ackermann function. For all practical purposes, the complexity is nearly linear, effectively O(N^2).

Space

O(N^2). The DSU data structure requires a parent array of size `4 * N * N`.

Trade-offs

Pros

More efficient in terms of both time and space complexity due to smaller constant factors.
Provides an elegant and scalable solution using a standard, powerful data structure.

Cons

The mapping of grid cells and their sub-regions to indices in the Union-Find data structure can be abstract and harder to visualize than the upscaling method.
Implementation of the Union-Find data structure adds a bit of overhead if not already available.

Solutions

Solution

1class Solution { private int [] p ; private int size ; public int regionsBySlashes ( String [] grid ) { int n = grid . length ; size = n * n * 4 ; p = new int [ size ]; for ( int i = 0 ; i < p . length ; ++ i ) { p [ i ] = i ; } for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int k = i * n + j ; if ( i < n - 1 ) { union ( 4 * k + 2 , ( k + n ) * 4 ); } if ( j < n - 1 ) { union ( 4 * k + 1 , ( k + 1 ) * 4 + 3 ); } char v = grid [ i ]. charAt ( j ); if ( v == '/' ) { union ( 4 * k , 4 * k + 3 ); union ( 4 * k + 1 , 4 * k + 2 ); } else if ( v == '\\' ) { union ( 4 * k , 4 * k + 1 ); union ( 4 * k + 2 , 4 * k + 3 ); } else { union ( 4 * k , 4 * k + 1 ); union ( 4 * k + 1 , 4 * k + 2 ); union ( 4 * k + 2 , 4 * k + 3 ); } } } return size ; } private int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } private void union ( int a , int b ) { int pa = find ( a ); int pb = find ( b ); if ( pa == pb ) { return ; } p [ pa ] = pb ; -- size ; } }

1/** * @param {string[]} grid * @return {number} */ function regionsBySlashes(2  grid,3) {4  const find = (x) => {5    if (p[x] !== x) {6      p[x] = find(p[x]);7    }8    return p[x];9  };10  const union = (a, b) => {11    const pa = find(a);12    const pb = find(b);13    if (pa !== pb) {14      p[pa] = pb;15      size--;16    }17  };18  const n = grid.length;19  let size = n * n * 4;20  const p = Array.from({ length: size }, (_, i) => i);21  for (let i = 0; i < n; i++) {22    for (let j = 0; j < n; j++) {23      const k = i * n + j;24      if (i < n - 1) {25        union(4 * k + 2, (k + n) * 4);26      }27      if (j < n - 1) {28        union(4 * k + 1, (k + 1) * 4 + 3);29      }30      if (grid[i][j] === " / ") {31        union(4 * k, 4 * k + 3);32        union(4 * k + 1, 4 * k + 2);33      } else if (grid[i][j] === " \\ ") {34        union(4 * k, 4 * k + 1);35        union(4 * k + 2, 4 * k + 3);36      } else {37        union(4 * k, 4 * k + 1);38        union(4 * k + 1, 4 * k + 2);39        union(4 * k + 2, 4 * k + 3);40      }41    }42  }43  return size;44}

1class Solution { public: vector < int > p ; int size ; int regionsBySlashes ( vector < string >& grid ) { int n = grid . size (); size = n * n * 4 ; p . resize ( size ); for ( int i = 0 ; i < size ; ++ i ) p [ i ] = i ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int k = i * n + j ; if ( i < n - 1 ) merge ( 4 * k + 2 , ( k + n ) * 4 ); if ( j < n - 1 ) merge ( 4 * k + 1 , ( k + 1 ) * 4 + 3 ); char v = grid [ i ][ j ]; if ( v == '/' ) { merge ( 4 * k , 4 * k + 3 ); merge ( 4 * k + 1 , 4 * k + 2 ); } else if ( v == '\\' ) { merge ( 4 * k , 4 * k + 1 ); merge ( 4 * k + 2 , 4 * k + 3 ); } else { merge ( 4 * k , 4 * k + 1 ); merge ( 4 * k + 1 , 4 * k + 2 ); merge ( 4 * k + 2 , 4 * k + 3 ); } } } return size ; } void merge ( int a , int b ) { int pa = find ( a ); int pb = find ( b ); if ( pa == pb ) return ; p [ pa ] = pb ; -- size ; } int find ( int x ) { if ( p [ x ] != x ) p [ x ] = find ( p [ x ]); return p [ x ]; } };

1class Solution : def regionsBySlashes ( self , grid : List [ str ]) -> int : def find ( x ): if p [ x ] != x : p [ x ] = find ( p [ x ]) return p [ x ] def union ( a , b ): pa , pb = find ( a ), find ( b ) if pa != pb : p [ pa ] = pb nonlocal size size -= 1 n = len ( grid ) size = n * n * 4 p = list ( range ( size )) for i , row in enumerate ( grid ): for j , v in enumerate ( row ): k = i * n + j if i < n - 1 : union ( 4 * k + 2 , ( k + n ) * 4 ) if j < n - 1 : union ( 4 * k + 1 , ( k + 1 ) * 4 + 3 ) if v == '/' : union ( 4 * k , 4 * k + 3 ) union ( 4 * k + 1 , 4 * k + 2 ) elif v == ' \\ ' : union ( 4 * k , 4 * k + 1 ) union ( 4 * k + 2 , 4 * k + 3 ) else : union ( 4 * k , 4 * k + 1 ) union ( 4 * k + 1 , 4 * k + 2 ) union ( 4 * k + 2 , 4 * k + 3 ) return size

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem