Beats 💯% | DSU 🌟 |
\n# Intuition\nThe problem is to determine the number of regions formed by slashes (\'/\' and \'\\') in a grid. The slashes divide a grid into different regions
![image.png](https://assets.leetcode.com/users/images/89103bb0-73de-4161-9433-c143e968af33_1723274551.8772507.png)\n# Intuition\nThe problem is to determine the number of regions formed by slashes (\'/\' and \'\\\') in a grid. The slashes divide a grid into different regions, and the goal is to count how many distinct regions there are.\n\n# Approach\n1. Union-Find (Disjoint Set Union):\n\n    - Concept: The grid can be thought of as a graph where each cell is connected to its neighboring cells. The slashes divide the grid into regions, and we can use Union-Find to group connected components (regions).\n    - Extended Grid: We treat the grid as a graph of nodes.     Each intersection of the original grid forms a node. So, for an n x n grid, we use an (n+1) x (n+1) grid of nodes.\n    - Boundary Connection: All boundary nodes (the edges of the grid) are connected to a virtual node. This helps in identifying when a slash creates a separate region.\n2. Union Operations:\n\n    - Traverse the grid:\n        - If there is a /, it connects the bottom-left corner with the top-right corner.\n        - If there is a \\, it connects the top-left corner with the bottom-right corner.\n    - If two nodes are already connected, the addition of a slash at that position creates a new region.\n3. Counting Regions:\n\n    - Each time a union operation connects two nodes that are already in the same set, it indicates the creation of a new region.\n# Complexity\n- Time Complexity: O((n+1)\xB2 * \u03B1((n+1)\xB2)), where \u03B1 is the inverse Ackermann function, which is nearly constant.\nWe are performing union-find operations on an (n+1) x (n+1) grid.\n- Space Complexity: O((n+1)\xB2).\nWe use additional space for the Union-Find parent array and to store the grid.\n# Code\n```C++ []\nclass Solution {\nprivate:\n    vector<int> p;\n    int cnt;\n    void dsu(int n1,int n2){\n        int up1 = findUp(n1);\n        int up2 = findUp(n2);\n        if(up1 == up2){\n            cnt++;\n            return;\n        }\n        p[up2] = up1;\n    }\n    int findUp(int node){\n        if(node==p[node]) return node;\n        return p[node] = findUp(p[node]);\n    }\npublic:\n    int regionsBySlashes(vector<string>& grid) {\n        int n = grid.size();\n        int nn = n+1;\n\n        p.resize(nn*nn);\n        cnt = 0;\n        for(int i=0; i<nn*nn; i++) p[i]=i;\n\n        for(int i=0; i<nn; i++){\n            for(int j=0; j<nn; j++){\n                if(i==0 || j==0 || i==n || j==n) \n                    dsu(0,i*nn+j);\n            }\n        }\n\n        for(int i=0; i<n; i++){\n            for(int j=0; j<n; j++){\n                if(grid[i][j] == \'/\'){\n                    dsu(  (i+1)*nn+j ,  i*nn+(j+1)  );\n                }else if(grid[i][j] != \' \'){\n                    dsu(  i*nn+j ,  (i+1)*nn+(j+1)  );\n                } \n            }\n        }\n        return cnt;\n    }\n};\n```\n```Java []\nclass Solution {\n    private int[] p;\n    private int cnt;\n\n    private void dsu(int n1, int n2) {\n        int up1 = findUp(n1);\n        int up2 = findUp(n2);\n        if (up1 == up2) {\n            cnt++;\n            return;\n        }\n        p[up2] = up1;\n    }\n\n    private int findUp(int node) {\n        if (node == p[node]) return node;\n        return p[node] = findUp(p[node]);\n    }\n\n    public int regionsBySlashes(String[] grid) {\n        int n = grid.length;\n        int nn = n + 1;\n\n        p = new int[nn * nn];\n        cnt = 0;\n        for (int i = 0; i < nn * nn; i++) p[i] = i;\n\n        for (int i = 0; i < nn; i++) {\n            for (int j = 0; j < nn; j++) {\n                if (i == 0 || j == 0 || i == n || j == n) \n                    dsu(0, i * nn + j);\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                    dsu((i + 1) * nn + j, i * nn + (j + 1));\n                } else if (grid[i].charAt(j) != \' \') {\n                    dsu(i * nn + j, (i + 1) * nn + (j + 1));\n                }\n            }\n        }\n        return cnt;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def findUp(self, node):\n        if node == self.p[node]:\n            return node\n        self.p[node] = self.findUp(self.p[node])\n        return self.p[node]\n\n    def dsu(self, n1, n2):\n        up1 = self.findUp(n1)\n        up2 = self.findUp(n2)\n        if up1 == up2:\n            self.cnt += 1\n        else:\n            self.p[up2] = up1\n\n    def regionsBySlashes(self, grid):\n        n = len(grid)\n        nn = n + 1\n\n        self.p = list(range(nn * nn))\n        self.cnt = 0\n\n        for i in range(nn):\n            for j in range(nn):\n                if i == 0 or j == 0 or i == n or j == n:\n                    self.dsu(0, i * nn + j)\n\n        for i in range(n):\n            for j in range(n):\n                if grid[i][j] == \'/\':\n                    self.dsu((i + 1) * nn + j, i * nn + (j + 1))\n                elif grid[i][j] != \' \':\n                    self.dsu(i * nn + j, (i + 1) * nn + (j + 1))\n\n        return self.cnt\n\n```\n```Javascript []\nvar regionsBySlashes = function(grid) {\n    const findUp = (node) => {\n        if (node === p[node]) return node;\n        return p[node] = findUp(p[node]);\n    };\n\n    const dsu = (n1, n2) => {\n        const up1 = findUp(n1);\n        const up2 = findUp(n2);\n        if (up1 === up2) {\n            cnt++;\n        } else {\n            p[up2] = up1;\n        }\n    };\n\n    const n = grid.length;\n    const nn = n + 1;\n    let cnt = 0;\n\n    const p = Array.from({ length: nn * nn }, (_, i) => i);\n\n    // Connect boundary nodes to a virtual node\n    for (let i = 0; i < nn; i++) {\n        for (let j = 0; j < nn; j++) {\n            if (i === 0 || j === 0 || i === n || j === n) {\n                dsu(0, i * nn + j);\n            }\n        }\n    }\n\n    // Process the grid\n    for (let i = 0; i < n; i++) {\n        for (let j = 0; j < n; j++) {\n            if (grid[i][j] === \'/\') {\n                dsu((i + 1) * nn + j, i * nn + (j + 1));\n            } else if (grid[i][j] === \'\\\\\') {\n                dsu(i * nn + j, (i + 1) * nn + (j + 1));\n            }\n        }\n    }\n\n    return cnt;\n};\n\n```\n![Please hit the upvote button (1).png](https://assets.leetcode.com/users/images/c5a36b39-e2c8-48fd-ad6d-c63c2ad2c1fb_1723274934.5034695.png)\n
['Array', 'Union Find', 'Matrix', 'Python', 'C++', 'Java', 'JavaScript']