Regions Cut By Slashes solution and explanation
Google
9 more videos on this problem
Regions Cut By Slashes - Leetcode 959 - PythonNeetCodeIO · 16:06 · 20K views
Leetcode 959 - Union Find | Region Cut By SlashesNideesh Terapalli · 9:20 · 15K views
Regions Cut By Slashes | Already Studied Concept | Easy Code | Leetcode 959 | codestorywithMIKcodestorywithMIK · 42:56 · 12K views
LeetCode 959. Regions Cut By Slashes Explanation and Solutionhappygirlzt · 12:33 · 7K views
✅ Regions Cut By Slashes - LeetCode 959 - Union Find - Optimized - Explained in DetailLeet Logics · 16:22 · 3K views
LeetCode 959. Regions Cut By Slashes | Union-find | PythonAlgoMonster · 3:26 · 3K views
Leetcode 959-Region cut by slashes | graphAbhishek Jaiswal · 25:07 · 1K views
959. Regions Cut By Slashes | DFS | Matrix | LeetCode + Full ExplanationCodeInBits · 31:58 · 939 views
Daily Leetcode #1593: Aug 10, 2024 - 959. Regions Cut By SlashesProgramming Live with Larry · 15:40 · 938 views
Regions Cut By Slashes (LeetCode 959) (DFS) (Graph)CodeWithARB · 31:24 · 591 views
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.
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' '.
Approach overview
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 1: Approach 1: Represent Each Grid Cell by a Subdivision into Smaller Triangles
In this approach, each 1x1 square is divided into four smaller triangles. The / and \ slashes correspond to boundaries between these triangles. We can represent these triangles using a graph and use DFS to count the number of connected components in this graph. Each connection between triangles denotes a passage within the same region.
def regionsBySlashes(grid):
n = len(grid)
graph = [[0] * (n * 3) for _ in range(n * 3)]
for i in range(n):
for j in range(n):
if grid[i][j] == '/':
graph[i * 3][j * 3 + 2] = 1
graph[i * 3 + 1][j * 3 + 1] = 1
graph[i * 3 + 2][j * 3] = 1
elif grid[i][j] == '\\':
graph[i * 3][j * 3] = 1
graph[i * 3 + 1][j * 3 + 1] = 1
graph[i * 3 + 2][j * 3 + 2] = 1
def dfs(x, y):
if 0 <= x < n * 3 and 0 <= y < n * 3 and graph[x][y] == 0:
graph[x][y] = 1
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for dx, dy in directions:
dfs(x + dx, y + dy)
regions = 0
for i in range(n * 3):
for j in range(n * 3):
if graph[i][j] == 0:
dfs(i, j)
regions += 1
return regionsclass Solution {
public int regionsBySlashes(String[] grid) {
int n = grid.length;
int[][] graph = new int[n * 3][n * 3];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i].charAt(j) == '/') {
graph[i * 3][j * 3 + 2] = 1;
graph[i * 3 + 1][j * 3 + 1] = 1;
graph[i * 3 + 2][j * 3] = 1;
}
else if (grid[i].charAt(j) == '\\') {
graph[i * 3][j * 3] = 1;
graph[i * 3 + 1][j * 3 + 1] = 1;
graph[i * 3 + 2][j * 3 + 2] = 1;
}
}
}
int regions = 0;
for (int i = 0; i < n * 3; ++i) {
for (int j = 0; j < n * 3; ++j) {
if (graph[i][j] == 0) {
dfs(graph, i, j);
regions++;
}
}
}
return regions;
}
private void dfs(int[][] graph, int x, int y) {
if (x < 0 || x >= graph.length || y < 0 || y >= graph[0].length || graph[x][y] == 1)
return;
graph[x][y] = 1;
dfs(graph, x + 1, y);
dfs(graph, x - 1, y);
dfs(graph, x, y + 1);
dfs(graph, x, y - 1);
}
}The implementation involves creating a larger 3n x 3n grid where each grid cell is expanded into a 3x3 grid based on present slashes. We then perform a DFS for each unvisited triangle marking it visited, effectively counting the disconnected regions in the grid.
Time Complexity: O((n * 3) * (n * 3)), where n is the grid size as we traverse each 3x3 cell.
Space Complexity: O((n * 3) * (n * 3)) due to the graph representation.
Approach 2: Approach 2: Union-Find to Track Regions
This approach uses the Union-Find data structure to manage and merge connected components. Each cell in the grid is broken into four triangles and represented as nodes in the DSU. Connectivity relationships are established and merged as per slashes present in the cell, and the number of disconnected regions is determined.
#include <vector>
#include <string>
class Solution {
private:
int find(std::vector<int>& parent, int x) {
if (parent[x] != x) parent[x] = find(parent, parent[x]);
return parent[x];
}
void unite(std::vector<int>& parent, std::vector<int>& rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
else if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
public:
int regionsBySlashes(std::vector<std::string>& grid) {
int n = grid.size();
int parts = n * n * 4;
std::vector<int> parent(parts);
std::vector<int> rank(parts, 0);
for (int i = 0; i < parts; ++i) parent[i] = i;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int base = 4 * (i * n + j);
char c = grid[i][j];
if (c != '/') {
unite(parent, rank, base, base + 1);
unite(parent, rank, base + 2, base + 3);
}
if (c != '\\') {
unite(parent, rank, base, base + 3);
unite(parent, rank, base + 1, base + 2);
}
// Unite with neighboring cells
if (j + 1 < n) unite(parent, rank, base + 2, 4 * (i * n + j + 1));
if (i + 1 < n) unite(parent, rank, base + 3, 4 * ((i + 1) * n + j) + 1);
}
}
int regions = 0;
for (int i = 0; i < parts; ++i) {
if (find(parent, i) == i) regions++;
}
return regions;
}
};var regionsBySlashes = function(grid) {
const n = grid.length;
const parent = Array(n * n * 4).fill(0).map((_, index) => index);
const find = x => parent[x] === x ? x : (parent[x] = find(parent[x]));
const union = (x, y) => {
const rootX = find(x);
const rootY = find(y);
if (rootX !== rootY) {
parent[rootY] = rootX;
}
};
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const base = 4 * (i * n + j);
const cell = grid[i][j];
if (cell !== '/') {
union(base, base + 1);
union(base + 2, base + 3);
}
if (cell !== '\\') {
union(base, base + 3);
union(base + 1, base + 2);
}
if (j + 1 < n) {
union(base + 2, 4 * (i * n + j + 1));
}
if (i + 1 < n) {
union(base + 3, 4 * ((i + 1) * n + j) + 1);
}
}
}
const regions = new Set();
for (let i = 0; i < parent.length; i++) {
regions.add(find(i));
}
return regions.size;
};The C++ solution employs the Union-Find data structure to manage the four sub-triangles per cell. It efficiently merges them based on the presence of slashes to identify distinct regions. The number of unique sets determines the count of regions.
Time Complexity: O(N^2 * α(N^2)), with α being a very slow-growing function (inverse Ackermann function), coming from the Union-Find operations.
Space Complexity: O(N^2) due to storing parent and rank structures for each cell division.
Approach 3: Union-Find
function regionsBySlashes(grid: string[]): number {
const find = (x: number) => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
const union = (a: number, b: number) => {
const pa = find(a);
const pb = find(b);
if (pa !== pb) {
p[pa] = pb;
size--;
}
};
const n = grid.length;
let size = n * n * 4;
const p = Array.from({ length: size }, (_, i) => i);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const 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 (grid[i][j] === '/') {
union(4 * k, 4 * k + 3);
union(4 * k + 1, 4 * k + 2);
} else if (grid[i][j] === '\\') {
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;
}func regionsBySlashes(grid []string) int {
n := len(grid)
size := n * n * 4
p := make([]int, size)
for i := range p {
p[i] = i
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
union := func(a, b int) {
pa, pb := find(a), find(b)
if pa == pb {
return
}
p[pa] = pb
size--
}
for i, row := range grid {
for j, v := range 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)
} 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
}Approach 4: DFS
function regionsBySlashes(grid: string[]): number {
const createGraph = () => {
const n = grid.length;
const g = Array.from({ length: n * 2 }, () => Array(n * 2).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const [y, x] = [i * 2, j * 2];
switch (grid[i][j]) {
case '/':
g[y][x] = g[y + 1][x + 1] = 0;
g[y][x + 1] = g[y + 1][x] = 1;
break;
case '\\':
g[y][x] = g[y + 1][x + 1] = 2;
g[y][x + 1] = g[y + 1][x] = 0;
break;
default:
g[y][x] = g[y][x + 1] = g[y + 1][x] = g[y + 1][x + 1] = 0;
break;
}
}
}
return g;
};
const isValid = (x: number) => 0 <= x && x < n;
const dfs = (i: number, j: number) => {
if (!isValid(i) || !isValid(j) || g[i][j]) return;
g[i][j] = -1;
const dirs = [-1, 0, 1, 0, -1];
const neighbours: number[] = [];
for (let d = 0; d < 4; d++) {
const [y, x] = [i + dirs[d], j + dirs[d + 1]];
if (isValid(y) && isValid(x)) {
dfs(y, x);
neighbours.push(g[y][x]);
} else {
neighbours.push(-1);
}
}
const [top, right, bottom, left] = neighbours;
if (top === 1 && right === 1) dfs(i - 1, j + 1);
if (bottom === 1 && left === 1) dfs(i + 1, j - 1);
if (top === 2 && left === 2) dfs(i - 1, j - 1);
if (bottom === 2 && right === 2) dfs(i + 1, j + 1);
};
const g = createGraph();
const n = g.length;
let res = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (g[i][j] === 0) {
dfs(i, j);
res++;
}
}
}
return res;
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Represent Each Grid Cell by a Subdivision into Smaller Triangles | Time Complexity: O((n * 3) * (n * 3)), where n is the grid size as we traverse each 3x3 cell. |
| Approach 2: Union-Find to Track Regions | Time Complexity: O(N^2 * α(N^2)), with α being a very slow-growing function (inverse Ackermann function), coming from the Union-Find operations. |
| Union-Find | – |
| DFS | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Regions Cut By Slashes easy or hard?
Regions Cut By Slashes is rated Medium difficulty on LeetCode with a high acceptance rate around 77%. The challenge lies in modeling the grid correctly rather than implementing complex algorithms. Once the cell subdivision idea or DSU mapping is clear, the implementation becomes straightforward.
How to solve Regions Cut By Slashes in O(n^2)?
Split each grid cell into four triangles and treat them as nodes in a graph. Connect triangles inside the cell depending on whether the character is '/', '\\', or space. Then connect boundary triangles with adjacent cells and run DFS/BFS to count connected components. This traversal visits each triangle once, giving O(n^2) time complexity.
Regions Cut By Slashes Python or Java solution
Python and Java implementations usually follow the triangle subdivision model. Each cell is expanded into four nodes, stored in arrays or adjacency relationships, and explored with DFS/BFS. Alternatively, a DSU structure unions triangles and counts unique parents after processing the grid.
What is the best approach for Regions Cut By Slashes?
Union-Find with cell subdivision into four triangles is the most common optimal approach. Each triangle becomes a node, and union operations connect triangles inside the cell and with neighboring cells. After processing the grid, the number of disjoint sets equals the number of regions. Time complexity is O(n^2 α(n)) with near-constant DSU operations.
Is Regions Cut By Slashes asked at Google/Amazon/Meta?
Grid connectivity and Union-Find problems like Regions Cut By Slashes appear frequently in interviews at companies such as Google, Amazon, and Meta. The problem tests graph modeling, connected components, and DSU implementation skills, which are common patterns in system-level algorithm interviews.
What data structure is used in Regions Cut By Slashes?
Two main data structures are used: graph traversal structures (for DFS or BFS) and Disjoint Set Union (Union-Find). The grid is typically modeled as four subcells per grid cell, and either traversal or DSU tracks connectivity between these regions.
What is the time complexity of Regions Cut By Slashes?
Both common solutions run in O(n^2) time because each grid cell is processed a constant number of times. The DFS/BFS subdivision approach explores up to 4*n*n nodes, while the Union-Find approach performs a constant number of union operations per cell. DSU operations add an inverse Ackermann factor α(n), which is effectively constant.