959. Regions Cut By Slashes
Regions Cut By Slashes (LeetCode 959) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.
How to solve Regions Cut By Slashes
Regions Cut By Slashes is a Union-Find problem, part of Graph Traversal Patterns (DFS & BFS). Master Union-Find data structure with path compression and union by rank for connectivity problems.
Work towards the solution in these steps:
- Think about representing each small square in the grid as multiple parts or nodes to better capture the divisions created by slashes.
- Consider modeling the problem as a graph where these parts are nodes, and edges represent connectivity between them within and across squares.
- Use a graph traversal algorithm like DFS or BFS to explore connected regions, counting distinct connected components as separate regions.
The reference solution runs in O(N^2) time and O(N^2) space.
The Regions Cut By Slashes solution and editorial walks through the full approach with reference code.
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, 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 ' '.
Topics and companies
Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union Find, Matrix.
Reported in interviews at Uber.
How to practise Regions Cut By Slashes on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N^2) time and O(N^2) space.
Open Regions Cut By Slashes in the code editor, or read the Regions Cut By Slashes editorial for a worked solution with its approach and complexity analysis.
Where Regions Cut By Slashes sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Union-Find (Disjoint Set Union - DSU) subpattern
- The full DSA patterns sheet
Problems related to Regions Cut By Slashes
Other problems that use the same Union-Find (Disjoint Set Union - DSU) and Graph Traversal Patterns (DFS & BFS) techniques:
- Accounts Merge — Medium, same subpattern
- Graph Valid Tree — Medium, same subpattern
- Greatest Common Divisor Traversal — Hard, same subpattern
- Largest Component Size by Common Factor — Hard, same subpattern
- Most Stones Removed with Same Row or Column — Medium, same subpattern
- Number of Connected Components in an Undirected Graph — Medium, same subpattern
Regions Cut By Slashes FAQ
What is the LeetCode number of Regions Cut By Slashes?
Regions Cut By Slashes is LeetCode problem 959, rated Medium.
What pattern is used to solve Regions Cut By Slashes?
Regions Cut By Slashes is a Union-Find problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.
What is the time complexity of Regions Cut By Slashes?
The reference solution runs in O(N^2) time and O(N^2) space.
Which companies ask Regions Cut By Slashes?
Regions Cut By Slashes has been reported in interviews at Uber.