Regions by slashes

XXX. Regions by Slashes

Union-Find

Graph

Problem Statement:

Given a n x n grid where each cell contains a slash ('/'), backslash ('\\'), or space (' '), determine the number of regions formed. A region is defined as a connected component of slashes, backslashes, or empty spaces, including the borders of the grid.

Example:

Input: [" /", "/ "] Output: 2 Explanation: The grid contains two regions due to the slashes dividing the grid into connected components.

Approach:

1. Model the grid as a graph where each cell corresponds to edges between points on its corners.
2. Use a Union-Find (disjoint-set) data structure to manage connections between points.
3. For each cell, interpret slashes ('/') and backslashes ('\\') as connections between specific corners:
   • '/' connects the top-right corner to the bottom-left corner.
   • '\\' connects the top-left corner to the bottom-right corner.
4. Iterate through the grid and attempt to "union" connected points.
5. If a "union" operation detects two points already in the same set, increment the region count.
6. Return the total number of regions formed.

Algorithm Intuition:

The problem is effectively about counting connected components in a graph. By treating the grid as a graph where corners are nodes and slashes/backslashes are edges, we can use Union-Find to group connected nodes. Each time we encounter a cycle in the graph, it indicates the presence of a new region.

Complexity:

Time Complexity: O(n² α(n²)), where n is the grid size and α is the inverse Ackermann function.
Space Complexity: O(n²), for the Union-Find data structure and grid points.

Java Implementation:

// Union-Find solution for Regions by Slashes
public class Solution {
    public int regionsBySlashes(String[] grid) {
        int gridSize = grid.length;
        int pointsPerSide = gridSize + 1;
        int totalPoints = pointsPerSide * pointsPerSide;

        // Initialize disjoint set data structure
        int[] parentArray = new int[totalPoints];
        Arrays.fill(parentArray, -1);

        // Connect border points
        for (int i = 0; i < pointsPerSide; i++) {
            for (int j = 0; j < pointsPerSide; j++) {
                if (i == 0 || j == 0 || i == pointsPerSide - 1 || j == pointsPerSide - 1) {
                    int point = i * pointsPerSide + j;
                    parentArray[point] = 0; // Union with border
                }
            }
        }

        // Set the parent of the top-left corner to itself
        parentArray[0] = -1;
        int regionCount = 1; // Start with one region (the border)

        // Process each cell in the grid
        for (int i = 0; i < gridSize; i++) {
            for (int j = 0; j < gridSize; j++) {
                // Treat each slash as an edge connecting two points
                if (grid[i].charAt(j) == '/') {
                    int topRight = i * pointsPerSide + (j + 1);
                    int bottomLeft = (i + 1) * pointsPerSide + j;
                    regionCount += union(parentArray, topRight, bottomLeft);
                } else if (grid[i].charAt(j) == '\\') {
                    int topLeft = i * pointsPerSide + j;
                    int bottomRight = (i + 1) * pointsPerSide + (j + 1);
                    regionCount += union(parentArray, topLeft, bottomRight);
                }
            }
        }

        return regionCount;
    }

    // Find the parent of a set
    private int find(int[] parentArray, int node) {
        if (parentArray[node] == -1) return node;
        return parentArray[node] = find(parentArray, parentArray[node]); // Path compression
    }

    // Union two sets and return 1 if a new region is formed, 0 otherwise
    private int union(int[] parentArray, int node1, int node2) {
        int parent1 = find(parentArray, node1);
        int parent2 = find(parentArray, node2);

        if (parent1 == parent2) {
            return 1; // Nodes are already in the same set, new region formed
        }

        parentArray[parent2] = parent1; // Union the sets
        return 0; // No new region formed
    }
}