Regions Cut by Slashes
Statement
An n × n grid is composed of n number of 1 × 1 squares, where each 1 × 1 square consists of a forward slash (/), back slash (\), or a blank space. These characters divide the square into adjacent regions. Given the grid represented as a string array, return the number of adjacent regions.
Constraints
- The grid consists of forward slashes (“/”), escaped back slashes (“\\”), and blank spaces (“ ”)
- 1 ≤
grid.length()≤ 30
Solution
"""
production algorithm
"""
class Solution:
def regions_cut_by_slashes(self, grid):
"""
time complexity O(mn)
space complexity O(mn)
"""
whitespace, backslash, forwardslash = "w", "b", "f"
grid = [row.replace(" ", whitespace)
.replace("\\", backslash)
.replace("/", forwardslash) for row in grid]
rows, columns = len(grid), len(grid[0])
size = rows * columns * 4
unionfind = UnionFind(size)
for row in range(rows):
for column in range(columns):
# connect regions of single square
north = self.get_north(row, column, columns)
east, south, west = north + 1, north + 2, north + 3
if grid[row][column] == whitespace:
unionfind.union(north, east)
unionfind.union(east, south)
unionfind.union(south, west)
if grid[row][column] == backslash:
unionfind.union(north, east)
unionfind.union(south, west)
if grid[row][column] == forwardslash:
unionfind.union(north, west)
unionfind.union(east, south)
# interconnect regions of multiple squares
next_north = south + self.get_next_north_distance(columns)
next_west = east + 6
if column < columns - 1:
unionfind.union(east, next_west)
if row < rows - 1:
unionfind.union(south, next_north)
return unionfind.count
def get_north(self, row, column, columns):
"""
time complexity O(1)
space complexity O(1)
"""
return (row * columns * 4) + (column * 4)
def get_next_north_distance(self, columns):
"""
time complexity O(1)
space complexity O(1)
"""
return self.get_north(1, 0, columns) - 2
class UnionFind:
def __init__(self, size):
self.parent = [n for n in range(size)]
self.size = [1 for _ in range(size)]
self.count = size
def find(self, x):
"""
time complexity O(⍺(n))
space complexity O(n)
"""
if not self.parent[x] == x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""
time complexity O(⍺(n))
space complexity O(n)
"""
rootx = self.find(x)
rooty = self.find(y)
if not rootx == rooty:
if self.size[rootx] < self.size[rooty]:
rooty, rootx = rootx, rooty
self.parent[rooty] = rootx
self.size[rootx] += self.size[rooty]
self.count -= 1"""
unit tests
"""
from unittest import TestCase
from algorithms.union_find.regions_cut_by_slashes.solution import Solution
class SolutionTestCase(TestCase):
def test_regions_cut_by_slashes(self):
# Given
grid = [" /\\ ", "//\\\\", "\\\\//", " \\/ "]
solution = Solution()
# When
actual = solution.regions_cut_by_slashes(grid)
# Then
expected = 6
self.assertEqual(actual, expected)Strategy
Union Find.
Explanation
Notice, that forward slashes and back slashes divide a square into regions. A forward slash separates a north and west region from a south and east region of a square. Also, a back slash separates a north and east region from a south and west region of a square. The algorithm will separate squares into north, south, east, and west regions in order to count the number of adjacent regions.
First, the algorithm transforms the grid. Blank spaces are mapped to the character “w”, escaped back slashes are mapped to the character “b”, and forward slashes are mapped to the character “f”. The grid is transformed so that each square of the grid maps to one character.
Next, the algorithm creates a UnionFind, where the size of the UnionFind is 4× the number of squares of the grid. This is how the algorithm represents the north, south, east, and west regions of each square of the grid. Then, the algorithm iterates each square of the grid.
For each square of the grid, the algorithm unions connected regions, and doesn’t union separated regions. Also, the algorithm unions connected regions across squares. It unions regions of the left and down squares with the current square.
After iteration completes, the algorithm has found the number of adjacent regions. The number of adjacent regions is the number of representatives of the UnionFind. The algorithm returns the number of adjacent regions.
Time Complexity
The algorithm iterates each square of the grid a constant number of times. First, the algorithm transforms the grid, and second, the algorithm unions regions of squares. For each iteration that the algorithm unions regions of squares, a constant number of UnionFind operations are done. Therefore, the time complexity of the algorithm is O(m × n × ⍺(m × n)), or simply O(m × n), where m and n are the number of rows and columns of the grid respectively, and ⍺(n) is the inverse Ackerman function that is the time complexity of UnionFind operations.
Space Complexity
The algorithm uses a UnionFind. The UnionFind uses auxiliary space with size that’s proportional to the number of squares of the grid. Therefore, the auxiliary space complexity of the algorithm is O(m × n).
