✅Beats 100% -Explained with [ Video ] -C++/Java/Python/JS - Union Find - Explained in Detail
\n\n# YouTube Video Explanation:\n\n### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail.\n\n **I
![Screenshot 2024-08-10 063008.png](https://assets.leetcode.com/users/images/af1d2b9e-766e-44aa-98d5-188c0a4a8d19_1723251633.6275167.png)\n\n# YouTube Video Explanation:\n\n### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail.\n\n<!-- **If you want a video for this question please write in the comments** -->\n\n\nhttps://youtu.be/JYw3FE3JisQ\n\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 2700 Subscribers*\n*Current Subscribers: 2641*\n\nFollow me on Instagram : https://www.instagram.com/divyansh.nishad/\n\n---\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves finding the number of regions formed by slashes (`/` and `\\`) in an `n x n` grid. The challenge is to consider how these slashes divide the grid and to count the number of separate regions they form.\n\nTo solve this problem, you can think of each cell in the grid as being divided into four triangles when considering the diagonals created by the slashes. The key idea is to model the problem as a graph where each triangle is a node, and adjacent triangles (those that are part of the same region) are connected by edges.\n\nHowever, instead of directly modeling triangles, we can model the problem using Union-Find (Disjoint Set Union, DSU). Each cell in the grid corresponds to four possible regions (upper left, upper right, lower left, lower right), and we\'ll use the Union-Find data structure to group connected regions together.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Initialization:**\n   - Create a Union-Find data structure to manage the connections between regions. Since the grid is `n x n`, we consider `n+1 x n+1` points to account for the boundaries and diagonals.\n\n2. **Connect the Boundaries:**\n   - Initialize the boundaries of the grid by connecting all outer points to a common root. This ensures that any region that touches the boundary will be connected.\n\n3. **Connect Regions Based on Slashes:**\n   - For each cell, determine the regions that are divided by slashes:\n     - A `\\` slash connects the lower left to the upper right.\n     - A `/` slash connects the upper left to the lower right.\n   - Use Union-Find to connect the corresponding regions.\n\n4. **Count Regions:**\n   - After processing all cells, the number of independent regions in the grid will be the count of unions formed when trying to connect already connected regions.\n\n# Complexity\n- **Time Complexity:**\n  - The Union-Find operations (union and find) are nearly constant time, i.e., \\(O(\u03B1(n))\\), where \\(\\alpha\\) is the inverse Ackermann function.\n  - Since we process each cell and potentially connect two regions per cell, the overall time complexity is \\(**O(n2\u22C5\u03B1(n)**)\\), where \\(n\\) is the size of the grid.\n\n- **Space Complexity:**\n  - We use an extra array to represent the union-find structure, which has a size proportional to the number of points, i.e., \\(O((n+1)^2)\\).\n\n\n\n# Explanation\nGiven an \\(n x n\\) grid where each cell contains either `/`, `\\`, or a space ` `, each of these characters divides the square into regions. The goal is to determine the number of regions formed by these characters.\n\n\n1. **Union-Find Data Structure**: \n   - **Purpose**: To efficiently manage and merge disjoint sets.\n   - **Components**: \n     - **Parent Array**: Tracks the parent of each element.\n     - **Rank Array**: Helps in balancing the tree structure.\n\n2. **Grid Representation**:\n   - Imagine each cell in the grid as a point on a larger grid of dots. For an \\(n x n\\) grid, we represent it as an \\((n+1) x (n+1)\\) grid of dots.\n\n3. **Initial Setup**:\n   - **Dots Array**: \n     - Each point on the grid is a node. We create a 1D array to represent these nodes.\n     - **Table 1**: Mapping of grid points to their corresponding 1D array indices.\n\n| Point (i, j) | Index in 1D Array |\n|--------------|-------------------|\n| (0, 0)       | 0                 |\n| (0, 1)       | 1                 |\n| (1, 0)       | 2                 |\n| ...          | ...               |\n| (n, n)       | \\(dots x dots - 1\\) |\n\n4. **Boundary Initialization**:\n   - **Purpose**: To ensure all boundary dots are connected to a single virtual root (0, 0).\n   - **Operation**: For each boundary dot, perform a union with the (0, 0) dot.\n   \n| Boundary Point | Operation    | Result |\n|----------------|--------------|--------|\n| (0, j)         | Union(0, j)  | Merged |\n| (i, 0)         | Union(0, i)  | Merged |\n| (n, j)         | Union(n, j)  | Merged |\n| (i, n)         | Union(i, n)  | Merged |\n\n5. **Processing Each Cell**:\n   - For each character in the grid:\n     - If it\'s `/`: Connect diagonal nodes.\n     - If it\'s `\\`: Connect opposite diagonal nodes.\n     \n   - **Table 2**: Actions based on cell content.\n\n| Cell Content | Connected Dots in 1D Array | Union Operation    |\n|--------------|----------------------------|--------------------|\n| `/`          | (i+1, j) and (i, j+1)       | Union(cell1, cell2) |\n| `\\`          | (i, j) and (i+1, j+1)       | Union(cell1, cell2) |\n\n6. **Counting Regions**:\n   - If two nodes that are already connected (i.e., have the same parent) are united again, it indicates an additional region.\n\n   - **Table 3**: Region counting.\n\n| Union Operation | Parent Before | Parent After | Regions Increment |\n|-----------------|---------------|--------------|-------------------|\n| Union(A, B)     | Different     | Same         | No                |\n| Union(A, B)     | Same          | Same         | Yes (Increment)   |\n\n\n### Summary\n\n- **Union-Find** is used to group connected regions in the grid.\n- Boundaries are connected initially to ensure regions touching the grid\'s edge are counted correctly.\n- Slashes in the grid determine which regions are connected or separated.\n- The final count gives the number of distinct regions in the grid.\n\n\n\n# Code\n```java []\nclass Solution {\n    int[] parent;\n    int[] rank;\n    int count;\n    public int regionsBySlashes(String[] grid) {\n        int rows = grid.length;\n        int dots = rows+1;\n        parent = new int[dots*dots];\n        rank = new int[dots*dots];\n        for (int i=0; i<parent.length; i++){\n            parent[i] = i;\n            rank[i] = 1;\n        }\n        \n        for (int i=0; i<dots; i++){\n            for (int j=0; j<dots; j++){\n                if (i==0 || j==0 || i==rows || j==rows){\n                    int cells = i * dots + j;\n                    union(0, cells);\n                }\n            }\n        }\n\n        for (int i=0; i<rows; i++){\n            char[] ch = grid[i].toCharArray();\n            for (int j=0; j<ch.length; j++){\n                if (ch[j] == \'\\\\\'){\n                    int cell1 = i* dots+ j;\n                    int cell2 = (i+1)*dots + (j+1);\n                    union(cell1, cell2);\n                } else if (ch[j] == \'/\'){\n                    int cell1 = (i+1)*dots + j;\n                    int cell2 = i*dots + (j+1);\n                    union(cell1, cell2);\n                }\n            }\n        }\n        return count;\n    }\n\n    public void union(int a, int b){\n        int parentA = find(a);\n        int parentB = find(b);\n        if (parentA == parentB){\n            count++;\n        } else {\n            if (rank[parentA] > rank[parentB]){\n                parent[parentB] = parentA;\n            } else if (rank[parentA] < rank[parentB]){\n                parent[parentA] = parentB;\n            } else {\n                parent[parentB] = parentA;\n                rank[parentA]++;\n            }\n        }\n    }\n\n    public int find(int a){\n        if(parent[a]==a)\n            return a;\n        int temp = find(parent[a]);\n        parent[a] = temp;\n        return temp;\n    }\n\n}\n```\n```C++ []\nclass Solution {\n    vector<int> parent;\n    vector<int> rank;\n    int count;\n    \npublic:\n    int regionsBySlashes(vector<string>& grid) {\n        int n = grid.size();\n        int dots = n + 1;\n        parent.resize(dots * dots);\n        rank.resize(dots * dots, 1);\n        count = 0;\n\n        // Initialize Union-Find structure\n        for (int i = 0; i < parent.size(); ++i) {\n            parent[i] = i;\n        }\n\n        // Connect boundaries to the top-left corner (0,0)\n        for (int i = 0; i < dots; ++i) {\n            for (int j = 0; j < dots; ++j) {\n                if (i == 0 || j == 0 || i == n || j == n) {\n                    int cell = i * dots + j;\n                    unionSets(0, cell);\n                }\n            }\n        }\n\n        // Process each cell and connect regions based on slashes\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < n; ++j) {\n                if (grid[i][j] == \'\\\\\') {\n                    int cell1 = i * dots + j;\n                    int cell2 = (i + 1) * dots + (j + 1);\n                    unionSets(cell1, cell2);\n                } else if (grid[i][j] == \'/\') {\n                    int cell1 = (i + 1) * dots + j;\n                    int cell2 = i * dots + (j + 1);\n                    unionSets(cell1, cell2);\n                }\n            }\n        }\n\n        return count;\n    }\n    \nprivate:\n    void unionSets(int a, int b) {\n        int parentA = find(a);\n        int parentB = find(b);\n        if (parentA == parentB) {\n            count++;\n        } else {\n            if (rank[parentA] > rank[parentB]) {\n                parent[parentB] = parentA;\n            } else if (rank[parentA] < rank[parentB]) {\n                parent[parentA] = parentB;\n            } else {\n                parent[parentB] = parentA;\n                rank[parentA]++;\n            }\n        }\n    }\n    \n    int find(int a) {\n        if (parent[a] == a) {\n            return a;\n        }\n        return parent[a] = find(parent[a]);\n    }\n};\n```\n```Python []\nclass Solution:\n    def __init__(self):\n        self.parent = []\n        self.rank = []\n        self.count = 0\n\n    def regionsBySlashes(self, grid):\n        n = len(grid)\n        dots = n + 1\n        self.parent = [i for i in range(dots * dots)]\n        self.rank = [1] * (dots * dots)\n\n        # Connect boundaries to the top-left corner (0,0)\n        for i in range(dots):\n            for j in range(dots):\n                if i == 0 or j == 0 or i == n or j == n:\n                    cell = i * dots + j\n                    self.union(0, cell)\n\n        # Process each cell and connect regions based on slashes\n        for i in range(n):\n            for j in range(n):\n                if grid[i][j] == \'\\\\\':\n                    cell1 = i * dots + j\n                    cell2 = (i + 1) * dots + (j + 1)\n                    self.union(cell1, cell2)\n                elif grid[i][j] == \'/\':\n                    cell1 = (i + 1) * dots + j\n                    cell2 = i * dots + (j + 1)\n                    self.union(cell1, cell2)\n\n        return self.count\n\n    def union(self, a, b):\n        parentA = self.find(a)\n        parentB = self.find(b)\n        if parentA == parentB:\n            self.count += 1\n        else:\n            if self.rank[parentA] > self.rank[parentB]:\n                self.parent[parentB] = parentA\n            elif self.rank[parentA] < self.rank[parentB]:\n                self.parent[parentA] = parentB\n            else:\n                self.parent[parentB] = parentA\n                self.rank[parentA] += 1\n\n    def find(self, a):\n        if self.parent[a] == a:\n            return a\n        self.parent[a] = self.find(self.parent[a])\n        return self.parent[a]\n```\n![upvote.png](https://assets.leetcode.com/users/images/9954b234-e874-4c0f-b4b8-853a568d0db8_1723251558.2098556.png)\n
['Array', 'Hash Table', 'Depth-First Search', 'Breadth-First Search', 'Union Find', 'Matrix', 'Python', 'C++', 'Java', 'JavaScript']