Regions Cut By Slashes
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' '
.
Solution
With the cutted sections, we will join the sections depending on the slashes. For example, '/' means that north
joins west
and south
joins east
.
Note that we must also join the north
region of a square to the south
region of the square to the top of it. Similar for the left square's east
region and current square's west
region.
This is best approached by DSU, in the very end after joining all sections, we just have to find the number of components in the map regions
.
Implementation
1def regionsBySlashes(grid: List[str]) -> int:
2 regions = {}
3 def find(x):
4 y = regions.get(x, x)
5 if y != x:
6 regions[x] = y = find(y)
7 return y
8 def union(x, y):
9 regions[find(x)] = find(y)
10
11 size = len(grid)
12 for i in range(size):
13 for j in range(size):
14 if i > 0: # connect square with top
15 union((i - 1, j, 'S'), (i, j, 'N'))
16 if j > 0: # connect square with left
17 union((i, j - 1, 'E'), (i, j, 'W'))
18 if grid[i][j] != "/": # ' ' or '\'
19 union((i, j, 'N'), (i, j, 'E')) # connect NE
20 union((i, j, 'S'), (i, j, 'W')) # connect SW
21 if grid[i][j] != "\\": # ' ' or '/'
22 union((i, j, 'N'), (i, j, 'W')) # connect NW
23 union((i, j, 'S'), (i, j, 'E')) # connect SE
24 return len(set(map(find, regions)))
Alternatively, we can find the number of connected components as in Number of Coneected Components, but bare in mind that we should only decrease the component count when we know that two elements aren't from the same set.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Solution Implementation
How does quick sort divide the problem into subproblems?
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.