Crack the Backend

Problem Statement

An n×n grid has each cell filled with one of " " (no slash), "/", or "\\". The slashes divide the grid into regions. Return the number of regions (connected areas).

Key Observations

UF on 4 sub-squares per cell: Split each cell into 4 triangles: top=0, right=1, bottom=2, left=3 (index 4*(i*n+j)+k). According to the character: " " — connect all 4; "/" — connect 0-3 and 1-2; "\" — connect 0-1 and 2-3. Then connect between adjacent cells: e.g. cell (i,j)'s top (0) with cell (i-1,j)'s bottom (2); left (3) with (i,j-1)'s right (1). Number of roots in UF = number of regions.

Approach

High-level: UF of size 4nn. For each cell (i,j): merge the 4 parts according to grid[i][j]; merge with neighbor cells (top↔above's bottom, left↔left's right). Return count of roots.

Steps: int N = 4nn; parent = new int[N]; for (i=0;i<N;i++) parent[i]=i; for (i=0;i<n;i++) for (j=0;j<n;j++) { int base = 4*(in+j); merge by char; if (i>0) union(base+0, 4((i-1)n+j)+2); if (j>0) union(base+3, 4(i*n+j-1)+1); } return count of roots;

Implementation

Java

public int regionsBySlashes(String[] grid) {
    int n = grid.length;
    int[] parent = new int[4 * n * n];

    for (int i = 0; i < parent.length; i++) {
        parent[i] = i;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int base = 4 * (i * n + j);
            char c = grid[i].charAt(j);

            if (c != '\\') { union(parent, base+0, base+3); union(parent, base+1, base+2); }
            if (c != '/') { union(parent, base+0, base+1); union(parent, base+2, base+3); }
            if (i > 0) {
                union(parent, base+0, base - 4*n + 2);
            }

            if (j > 0) {
                union(parent, base+3, base - 4 + 1);
            }
        }
    }

    int count = 0;

    for (int i = 0; i < parent.length; i++) {
        if (find(parent, i) == i) {
            count++;
        }
    }

    return count;
}

Test Cases

Example 1

Input

[" /","/ "]

Expected

2

Explanation

2 regions.

Complexity Analysis

Time: O(n α(n)) ≈ O(n).
Space: O(n).

Follow-ups

Path compression + rank for optimal UF.