🌟 Solving the Slashes Conundrum in Multiple Languages 🔥💯
\n\nExplore a collection of solutions to LeetCode problems in multiple programming languages. Each solution includes a detailed explanation and step-by-step app
![Screenshot 2024-07-02 113653.png](https://assets.leetcode.com/users/images/9def2eb5-9a04-4bcf-89ca-ec0a1372ab8d_1723261788.284309.png)\n\nExplore a collection of solutions to LeetCode problems in multiple programming languages. Each solution includes a detailed explanation and step-by-step approach to solving the problem efficiently. Whether you\'re a beginner looking to learn or an experienced coder seeking optimized solutions, this repository aims to provide clear and insightful approaches to tackling challenging LeetCode problems.\n\n### **Access daily LeetCode Solutions Repo :** [click here](https://github.com/withaarzoo/LeetCode-Solutions)\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/9b5d77cb-5e7e-4490-ad25-b3e0aa7ea42d_1723261774.2735398.png)\n\n---\n\n# Intuition\n<!-- Describe your initial thoughts and strategy to solve this problem. -->\nThe problem asks us to count the number of distinct regions formed by slashes (`/`, `\\`) in an `n x n` grid. Each cell can be divided into 4 parts, and depending on the slashes, these parts connect differently. The goal is to simulate these connections and count the distinct regions.\n\nThe key observation is that each grid cell can be thought of as being split into four triangles, and the slashes determine which triangles are connected. By treating the grid this way, we can apply a union-find (or DFS/BFS) algorithm to count the distinct regions.\n\n# Approach\n<!-- Detail the specific method and steps you used to solve the problem. -->\n1. **Grid Representation:** Treat each cell in the grid as four parts (triangles). Number them as 0, 1, 2, and 3 (top-left, top-right, bottom-right, bottom-left).\n2. **Union-Find:** Use a union-find data structure to merge the triangles within a cell based on the slashes and connect triangles across adjacent cells.\n3. **Merge Cells:** For each `/`, connect the top-left with the bottom-right, and the top-right with the bottom-left. For each `\\`, connect the top-right with the bottom-left. For spaces (` `), connect all four triangles.\n4. **Count Regions:** After processing the grid, count the number of disjoint sets in the union-find structure to determine the number of regions.\n\n# Complexity\n- **Time complexity:** \n  - $$O(n^2 \\log n)$$ where \\(n\\) is the size of the grid. The log factor comes from the union-find operations.\n\n- **Space complexity:**\n  - $$O(n^2)$$ for the union-find structure, which stores the parent and rank of each triangle.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int regionsBySlashes(vector<string>& grid) {\n        int n = grid.size();\n        vector<int> parent(4 * n * n), rank(4 * n * n, 0);\n        \n        // Initialize the union-find structure\n        iota(parent.begin(), parent.end(), 0);\n\n        // Find function with path compression\n        function<int(int)> find = [&](int x) {\n            return parent[x] == x ? x : parent[x] = find(parent[x]);\n        };\n\n        // Union function with union by rank\n        auto unite = [&](int x, int y) {\n            int rootX = find(x), rootY = find(y);\n            if (rootX != rootY) {\n                if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;\n                else if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;\n                else {\n                    parent[rootY] = rootX;\n                    rank[rootX]++;\n                }\n            }\n        };\n\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < n; ++j) {\n                int base = 4 * (i * n + j);\n                char c = grid[i][j];\n                \n                // Connect the parts inside the current cell\n                if (c == \'/\') {\n                    unite(base, base + 3);\n                    unite(base + 1, base + 2);\n                } else if (c == \'\\\\\') {\n                    unite(base, base + 1);\n                    unite(base + 2, base + 3);\n                } else {\n                    unite(base, base + 1);\n                    unite(base + 1, base + 2);\n                    unite(base + 2, base + 3);\n                }\n\n                // Connect with the right cell\n                if (j + 1 < n) {\n                    unite(base + 1, base + 7);\n                }\n                \n                // Connect with the cell below\n                if (i + 1 < n) {\n                    unite(base + 2, base + 4 * n);\n                }\n            }\n        }\n\n        // Count distinct regions\n        int regions = 0;\n        for (int i = 0; i < 4 * n * n; ++i) {\n            if (find(i) == i) regions++;\n        }\n        return regions;\n    }\n};\n\n```\n```Java []\nclass Solution {\n    public int regionsBySlashes(String[] grid) {\n        int n = grid.length;\n        int[] parent = new int[4 * n * n];\n        int[] rank = new int[4 * n * n];\n\n        // Initialize the union-find structure\n        for (int i = 0; i < parent.length; i++) {\n            parent[i] = i;\n        }\n\n        // Find with path compression\n        int find(int x) {\n            if (parent[x] != x) {\n                parent[x] = find(parent[x]);\n            }\n            return parent[x];\n        }\n\n        // Union with union by rank\n        void unite(int x, int y) {\n            int rootX = find(x);\n            int rootY = find(y);\n            if (rootX != rootY) {\n                if (rank[rootX] > rank[rootY]) {\n                    parent[rootY] = rootX;\n                } else if (rank[rootX] < rank[rootY]) {\n                    parent[rootX] = rootY;\n                } else {\n                    parent[rootY] = rootX;\n                    rank[rootX]++;\n                }\n            }\n        }\n\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < n; ++j) {\n                int base = 4 * (i * n + j);\n                char c = grid[i].charAt(j);\n                \n                // Connect the parts inside the current cell\n                if (c == \'/\') {\n                    unite(base, base + 3);\n                    unite(base + 1, base + 2);\n                } else if (c == \'\\\\\') {\n                    unite(base, base + 1);\n                    unite(base + 2, base + 3);\n                } else {\n                    unite(base, base + 1);\n                    unite(base + 1, base + 2);\n                    unite(base + 2, base + 3);\n                }\n\n                // Connect with the right cell\n                if (j + 1 < n) {\n                    unite(base + 1, base + 7);\n                }\n                \n                // Connect with the cell below\n                if (i + 1 < n) {\n                    unite(base + 2, base + 4 * n);\n                }\n            }\n        }\n\n        // Count distinct regions\n        int regions = 0;\n        for (int i = 0; i < 4 * n * n; ++i) {\n            if (find(i) == i) regions++;\n        }\n        return regions;\n    }\n}\n\n```\n```JavaScript []\n/**\n * @param {string[]} grid\n * @return {number}\n */\nvar regionsBySlashes = function(grid) {\n    const n = grid.length;\n    const parent = Array.from({ length: 4 * n * n }, (_, i) => i);\n    const rank = Array(4 * n * n).fill(0);\n\n    // Find with path compression\n    function find(x) {\n        if (parent[x] !== x) {\n            parent[x] = find(parent[x]);\n        }\n        return parent[x];\n    }\n\n    // Union with union by rank\n    function unite(x, y) {\n        const rootX = find(x);\n        const rootY = find(y);\n        if (rootX !== rootY) {\n            if (rank[rootX] > rank[rootY]) {\n                parent[rootY] = rootX;\n            } else if (rank[rootX] < rank[rootY]) {\n                parent[rootX] = rootY;\n            } else {\n                parent[rootY] = rootX;\n                rank[rootX]++;\n            }\n        }\n    }\n\n    for (let i = 0; i < n; i++) {\n        for (let j = 0; j < n; j++) {\n            const base = 4 * (i * n + j);\n            const c = grid[i][j];\n\n            // Connect the parts inside the current cell\n            if (c === \'/\') {\n                unite(base, base + 3);\n                unite(base + 1, base + 2);\n            } else if (c === \'\\\\\') {\n                unite(base, base + 1);\n                unite(base + 2, base + 3);\n            } else {\n                unite(base, base + 1);\n                unite(base + 1, base + 2);\n                unite(base + 2, base + 3);\n            }\n\n            // Connect with the right cell\n            if (j + 1 < n) {\n                unite(base + 1, base + 7);\n            }\n\n            // Connect with the cell below\n            if (i + 1 < n) {\n                unite(base + 2, base + 4 * n);\n            }\n        }\n    }\n\n    // Count distinct regions\n    let regions = 0;\n    for (let i = 0; i < 4 * n * n; i++) {\n        if (find(i) === i) regions++;\n    }\n    return regions;\n};\n\n```\n```Python []\nclass Solution:\n    def regionsBySlashes(self, grid: List[str]) -> int:\n        n = len(grid)\n        # Each cell is divided into 4 parts, so we create a union-find (disjoint-set) array for 4 * n * n elements\n        parent = list(range(4 * n * n))\n        rank = [0] * (4 * n * n)\n\n        # Find function with path compression\n        def find(x):\n            if parent[x] != x:\n                parent[x] = find(parent[x])\n            return parent[x]\n\n        # Union function with union by rank\n        def unite(x, y):\n            rootX = find(x)\n            rootY = find(y)\n            if rootX != rootY:\n                if rank[rootX] > rank[rootY]:\n                    parent[rootY] = rootX\n                elif rank[rootX] < rank[rootY]:\n                    parent[rootX] = rootY\n                else:\n                    parent[rootY] = rootX\n                    rank[rootX] += 1\n\n        for i in range(n):\n            for j in range(n):\n                base = 4 * (i * n + j)\n                c = grid[i][j]\n\n                # Connect the parts inside the current cell\n                if c == \'/\':\n                    unite(base, base + 3)  # Connect top-left with bottom-right\n                    unite(base + 1, base + 2)  # Connect top-right with bottom-left\n                elif c == \'\\\\\':\n                    unite(base, base + 1)  # Connect top-left with top-right\n                    unite(base + 2, base + 3)  # Connect bottom-left with bottom-right\n                else:\n                    unite(base, base + 1)  # Connect all four parts\n                    unite(base + 1, base + 2)\n                    unite(base + 2, base + 3)\n\n                # Connect with the right cell (if exists)\n                if j + 1 < n:\n                    unite(base + 1, 4 * (i * n + (j + 1)))\n\n                # Connect with the cell below (if exists)\n                if i + 1 < n:\n                    unite(base + 2, 4 * ((i + 1) * n + j))\n\n        # Count the number of distinct regions (roots in the union-find structure)\n        regions = sum(find(i) == i for i in range(4 * n * n))\n        return regions\n\n```\n```Go []\nfunc regionsBySlashes(grid []string) int {\n    n := len(grid)\n    parent := make([]int, 4 * n * n)\n    rank := make([]int, 4 * n * n)\n\n    // Initialize the union-find structure\n    for i := 0; i < len(parent); i++ {\n        parent[i] = i\n    }\n\n    // Find function with path compression\n    var find func(x int) int\n    find = func(x int) int {\n        if parent[x] != x {\n            parent[x] = find(parent[x])\n        }\n        return parent[x]\n    }\n\n    // Union function with union by rank\n    unite := func(x, y int) {\n        rootX := find(x)\n        rootY := find(y)\n        if rootX != rootY {\n            if rank[rootX] > rank[rootY] {\n                parent[rootY] = rootX\n            } else if rank[rootX] < rank[rootY] {\n                parent[rootX] = rootY\n            } else {\n                parent[rootY] = rootX\n                rank[rootX]++\n            }\n        }\n    }\n\n    for i := 0; i < n; i++ {\n        for j := 0; j < n; j++ {\n            base := 4 * (i * n + j)\n            c := grid[i][j]\n\n            // Connect the parts inside the current cell\n            if c == \'/\' {\n                unite(base, base+3)\n                unite(base+1, base+2)\n            } else if c == \'\\\\\' {\n                unite(base, base+1)\n                unite(base+2, base+3)\n            } else {\n                unite(base, base+1)\n                unite(base+1, base+2)\n                unite(base+2, base+3)\n            }\n\n            // Connect with the right cell\n            if j+1 < n {\n                unite(base+1, base+7)\n            }\n\n            // Connect with the cell below\n            if i+1 < n {\n                unite(base+2, base+4*n)\n            }\n        }\n    }\n\n    // Count distinct regions\n    regions := 0\n    for i := 0; i < 4 * n * n; i++ {\n        if find(i) == i {\n            regions++\n        }\n    }\n\n    return regions\n}\n\n```\n\n\n# Step-by-Step Detailed Explanation\n\n1. **Initialization:**\n   - We initialize a union-find (or disjoint-set) structure where each cell in the `n x n` grid is divided into four parts (or triangles). These triangles are represented as individual elements in the union-find structure.\n   - We also initialize a `rank` array to optimize the union-find operations.\n\n2. **Grid Traversal:**\n   - We iterate over each cell in the grid. For each cell, depending on whether it contains a `/`, `\\`, or a space (` `), we connect the corresponding triangles using the union operation.\n   - For a `/`, the top-left and bottom-right triangles are connected, as are the top-right and bottom-left triangles.\n   - For a `\\`, the top-right and bottom-left triangles are connected, as are the top-left and bottom-right triangles.\n   - If the cell is a space (` `), all four triangles are connected.\n\n3. **Adjacent Cells Connection:**\n   - We also connect triangles between adjacent cells. For example, the right edge of one cell connects with the left edge of the cell to its right, and the bottom edge of one cell connects with the top edge of the cell below it.\n\n4. **Counting Regions:**\n   - After processing the entire grid, the number of distinct regions is determined by counting the number of disjoint sets in the union-find structure. Each set represents a unique region.\n\n---\n\n![upvote cat.png](https://assets.leetcode.com/users/images/517ef84c-eea6-4b5e-b1a7-8066f1c15c51_1723262053.7999027.png)\n
['Array', 'Hash Table', 'Depth-First Search', 'Breadth-First Search', 'Python', 'C++', 'Java', 'Go', 'Python3', 'JavaScript']