The O(n) Club: Regions Cut By Slashes — Triangles, Therapy, and Union-Find

The O(n) Club: Regions Cut By Slashes — Triangles, Therapy, and Union-Find

⚡ TL;DR

If your plan is to manually color each region, pour some coffee and pack a lunch. Instead, break every cell into four triangles, connect triangles based on slashes, and run Union-Find like a therapist uniting bickering sitcom families. Your result? Count the connected groups at the end—done.

// Short and sweet:
int regions = regionsBySlashes(grid);

🧠 How Devs Usually Mess This Up

First, someone tries standard DFS or BFS, marching through the grid as if diagonals were a myth. Then the slashes show up and reality hits—those diagonal cuts create and split regions in non-Euclidean ways. Adjacency is now a suggestion, and algorithms go chasing phantom boundaries. If your recursion starts hallucinating, you’re not alone.

🔍 What’s Actually Going On

Each cell is like a slice of pizza. Except this pizza gets sliced diagonally, and sometimes not at all. The trick: subdivide every cell into four triangles (think top, right, bottom, left corners). With slashes, you’re not “coloring blocks”—you’re asking which triangles are roomies. Union-Find grabs triangles that belong together—even across cells—so you count the number of friend groups left. No geometry textbook, just index math and data structure magic.

🛠️ PseudoCode

• For each cell at (i, j):
  • Label four triangles per cell: cell(i, j), triangle 0-3 (top, right, bottom, left)
  • Inside the cell:
    • If blank space: union all four triangles.
    • If ‘/’, unite top & left, and right & bottom triangles.
      (This slices the square like a forward slash on your keyboard.)
    • If ‘\\’, unite top & right, and left & bottom triangles.
      A classic backslash party.
  • Between cells:
    • Union the bottom triangle of (i, j) with the top triangle of (i+1, j)
    • Union the right triangle of (i, j) with the left triangle of (i, j+1)
• At the end, the number of unique parent triangles left = regions.

💻 The Code

public int regionsBySlashes(String[] grid) {
    int n = grid.length;
    int size = n * n * 4;
    UnionFind uf = new UnionFind(size);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int root = (i * n + j) * 4;
            char val = grid[i].charAt(j);
            // Inside this cell
            if (val == ' ') {
                uf.union(root + 0, root + 1);
                uf.union(root + 1, root + 2);
                uf.union(root + 2, root + 3);
            } else if (val == '/') {
                uf.union(root + 0, root + 3); // top & left
                uf.union(root + 1, root + 2); // right & bottom
            } else if (val == '\\') {
                uf.union(root + 0, root + 1); // top & right
                uf.union(root + 2, root + 3); // bottom & left
            }
            // With below cell
            if (i + 1 < n) {
                int down = ((i + 1) * n + j) * 4;
                uf.union(root + 2, down + 0);
            }
            // With right cell
            if (j + 1 < n) {
                int right = (i * n + (j + 1)) * 4;
                uf.union(root + 1, right + 3);
            }
        }
    }
    return uf.count();
}
 class UnionFind {
    int[] parent;
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union(int x, int y) {
        parent[find(x)] = find(y);
    }
    int count() {
        int count = 0;
        for (int i = 0; i < parent.length; i++) {
            if (parent[i] == i) count++;
        }
        return count;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Java Backslash: It’s ‘\\’. If you used just ‘\’, the compiler’s about to roast you.
• Inter-cell links: If you only unite triangles inside single cells, regions will leak across cell boundaries—or worse, you’ll miss connections.
• Time/Space: O(n²) for almost everything thanks to the friendly neighborhood Union-Find. No grid inflation, no drama.
• Don’t use real geometry: No, you don’t actually draw lines. It’s just index juggling and triangle gossip.

🧠 Interviewer Brain-Tattoo

“When geometry gets messy, turn it into graph theory and let Union-Find handle your group therapy sessions.”