DCC - 10 AUG 2024 || DSU
Approach Intuition:\n\nThe problem of counting regions formed by slashes (/) and backslashes (\\) in a grid can be tackled using a Disjoint Set (Union-Find) app
### Approach Intuition:\n\nThe problem of counting regions formed by slashes (`/`) and backslashes (`\\`) in a grid can be tackled using a Disjoint Set (Union-Find) approach. The key idea is to treat each cell in the grid as a collection of points that need to be connected based on the slashes.\n\n#### Detailed Steps:\n1. **Grid Representation:**\n   - The grid is represented as a collection of points in a `(n+1) x (n+1)` matrix, where `n` is the length of the grid. This ensures that every cell in the grid corresponds to points in this matrix.\n\n2. **Boundary Handling:**\n   - All boundary points (points on the edges of the grid) are connected to a virtual root (point `(0, 0)`) to represent the infinite external region. This is crucial for counting enclosed regions formed by slashes.\n\n3. **Union-Find Operations:**\n   - As you traverse the grid, you perform union operations between specific points based on whether the character is a slash `/` or backslash `\\`.\n   - If the current grid cell contains a slash `/`, the points `(i+1, j)` and `(i, j+1)` are connected.\n   - If the grid cell contains a backslash `\\`, the points `(i, j)` and `(i+1, j+1)` are connected.\n   - If a union operation tries to connect two points that are already connected, it implies the formation of a new region, so the `count` is incremented.\n\n4. **Counting Regions:**\n   - The `count` variable keeps track of the number of regions formed. Initially set to 1 (since we start with one external region), it is incremented whenever a union operation connects points that are already in the same set, indicating an additional region.\n\n### Complexity Analysis:\n\n1. **Time Complexity:**\n   - **Union-Find Operations:** Each union and find operation has an amortized time complexity of \\(O(alpha(N^2))\\), where \\(alpha\\) is the inverse Ackermann function, which grows very slowly.\n   - **Total Operations:** Since there are \\(O(n^2)\\) cells in the grid, and each may result in a constant number of union-find operations, the total time complexity is \\(O(N^2*alpha(N^2))\\), where \\(N = n+1\\).\n\n2. **Space Complexity:**\n   - **Disjoint Set Data Structure:** The space complexity is \\(O(N^2)\\) to store the `parent` and `size` arrays for all points in the grid.\n   - The space complexity primarily depends on the size of the grid, resulting in \\(O((n+1)^2)\\) space usage.\n\n### Summary:\nThis approach efficiently counts the number of regions formed by slashes and backslashes in a grid using a Union-Find data structure. The algorithm effectively handles the boundary cases and correctly identifies when a new region is formed, providing an optimal solution in both time and space complexity for this problem.\n\n# Code\n```\nclass DisjointSet {\n    List<Integer> parent = new ArrayList<>();\n    List<Integer> size = new ArrayList<>();\n    int count;\n\n    public DisjointSet(int n) {\n        for (int i = 0; i < n; i++) {\n            parent.add(i);\n            size.add(1);\n        }\n        count=1;\n    }\n\n    public int find_parent(int node) {\n        if (node == parent.get(node)) return node;\n        int root = find_parent(parent.get(node));\n        parent.set(node, root); \n        return root;\n    }\n\n    public void unionBySize(int u, int v) {\n        int rootU = find_parent(u);\n        int rootV = find_parent(v);\n\n        if (rootU == rootV) {\n            // Increment count if both nodes are already in the same set\n            count++;\n            return;\n        }\n\n        if (size.get(rootU) < size.get(rootV)) {\n            parent.set(rootU, rootV);\n            size.set(rootV, size.get(rootV) + size.get(rootU));\n        } else {\n            parent.set(rootV, rootU);\n            size.set(rootU, size.get(rootU) + size.get(rootV));\n        }\n    }\n}\n\nclass Solution {\n    public int regionsBySlashes(String[] grid) {\n        int n = grid.length;\n        int N = n + 1;\n        DisjointSet ds = new DisjointSet(N * N);\n\n        \n       for(int i=0;i<n+1;i++){\n            for(int j=0;j<n+1;j++){\n                if(i==0||j==0||i==n||j==n){\n                    int col = (n+1)*i+j;\n                    if(col!=0)\n                    ds.unionBySize(0,col);\n                }\n            }\n        }\n\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                if(grid[i].charAt(j)==\'/\'){\n                    int p1 = (i+1)*(n+1) + j;\n                    int p2 = i*(n+1) + j+1; \n                    ds.unionBySize(p1,p2);\n                    \n                }\n                else if(grid[i].charAt(j)==\'\\\\\'){\n                     int p1 = i*(n+1) + j;\n                    int p2 = (i+1)*(n+1) + j+1;\n                    ds.unionBySize(p1,p2);\n                }\n            }\n        }\n\n        return ds.count;\n    }\n}\n\n\n```
['Union Find', 'Java']