How hard is LeetCode 959. Regions Cut By Slashes?

LeetCode 959. Regions Cut By Slashes is rated Medium on LeetCode.

What is the time complexity of LeetCode 959. Regions Cut By Slashes?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 959. Regions Cut By Slashes?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 959. Regions Cut By Slashes cover?

LeetCode 959. Regions Cut By Slashes is tagged Depth-First Search, Breadth-First Search, Union Find, Array, Hash Table and Matrix on LeetCode.

Regions Cut By Slashes — LeetCode 959 Python Solution

MediumDepth-First SearchBreadth-First SearchUnion FindArrayHash TableMatrix

Problem: #959
Pattern: Union-Find
Reading time: 6 min
Source: leetcode.com

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.

Example

Input: grid = [" /","/ "]
Output: 2

Python solution

Python

class 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

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 959. Regions Cut By Slashes is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 959. Regions Cut By Slashes?: LeetCode 959. Regions Cut By Slashes is rated Medium on LeetCode.
What is the time complexity of LeetCode 959. Regions Cut By Slashes?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 959. Regions Cut By Slashes?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 959. Regions Cut By Slashes cover?: LeetCode 959. Regions Cut By Slashes is tagged Depth-First Search, Breadth-First Search, Union Find, Array, Hash Table and Matrix on LeetCode.