Regions Cut By Slashes

Leetcode Link

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

def regionsBySlashes(grid: List[str]) -> int:
    regions = {}
    def find(x):
        y = regions.get(x, x)
        if y != x:
            regions[x] = y = find(y)
        return y
    def union(x, y):
        regions[find(x)] = find(y)

    size = len(grid)
    for i in range(size):
        for j in range(size):
            if i > 0:           # connect square with top
                union((i - 1, j, 'S'), (i, j, 'N'))
            if j > 0:           # connect square with left
                union((i, j - 1, 'E'), (i, j, 'W'))
            if grid[i][j] != "/":             # ' ' or '\'
                union((i, j, 'N'), (i, j, 'E'))   # connect NE
                union((i, j, 'S'), (i, j, 'W'))   # connect SW
            if grid[i][j] != "\\":            # ' ' or '/'
                union((i, j, 'N'), (i, j, 'W'))   # connect NW
                union((i, j, 'S'), (i, j, 'E'))   # connect SE
    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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know

Regions Cut By Slashes

Solution

Implementation

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Recommended Readings