Python | Convert to Classic Union Find | Interview Explanation
The objective of my article is not to provide the fastest way to solve this problem.\nThere are articles by many other which are faster than this.\nThe objectiv
The objective of my article is not to provide the fastest way to solve this problem.\nThere are articles by many other which are faster than this.\nThe objective of this article is to **make minimal changes to a union find template to solve the problem**\n\nMy intuition:\nI have solved the classic union find problem of largest land body.\nLink: https://leetcode.com/problems/number-of-islands/\n**Note:** highly recommend you to solve this first as the intuition becomes easier\n\nProblem breakdown:\n1. Find **largest land body**.\n2. Find which **water body to convert**. (This can be broken down further)\n\nNow, I have already **solved step 1 in the question above**.\nOnly need to check for step 2.\n\n**Breaking down step 2** into more managable chunks:\n1. Check for a water body\n2. Check it\'s **unique neighbours**\n3. **Sum the size** of the unique neighbours\n4. **Add 1 to this sum** as we converted this water body to land\n\n\nHope my code explains how I am performing all these steps.\nI have used the word **"standard"** to indicate that this can be replaced by any other union find template function.\n**Note: This can be performed for any rectangular grid too**\n```\nclass Solution:\n    def largestIsland(self, grid: List[List[int]]) -> int:\n        m, n = len(grid), len(grid[0])\n        # parent array to keey track\n        parent = list(range(m*n))\n        # rank array used for union by rank and size calculation\n        rank = [1 for _ in range(m*n)]\n        \n        # standard DSU find function\n        def find(x):\n            while x != parent[x]:\n                parent[x] = parent[parent[x]]\n                x = parent[x]\n            return x\n        \n        # standard DSU union by rank function\n        def union(x,y):\n            parX, parY = find(x), find(y)\n            if parX == parY: return\n            if rank[parX] >= rank[parY]:\n                rank[parX] += rank[parY]\n                parent[parY] = parX\n            else:\n                rank[parY] += rank[parX]\n                parent[parX] = parY\n    \n        # Step 1: join the land\n\n        # for each island we perform union operation\n        for i, row in enumerate(grid):\n            for j, val in enumerate(row):\n                \n                # important condition: if we have a water body, we set its rank to 0 (will be used in the next step)\n                if not val: \n                    rank[i*m+j] = 0\n                    continue\n                \n                # performing union of land bodies\n                for x,y in [(i-1, j),(i+1, j),(i, j+1),(i, j-1)]:\n                    # outside of grid check\n                    if not (0 <= x < m and 0 <= y < n): continue\n                    \n                    if grid[x][y]: union(i*m+j, x*m+y)\n        \n        # Step 2: convert a water body (if present)\n        \n        # the minimum final ans will always be the size of the largest land present \n        ans = max(rank)\n        for i, row in enumerate(grid):\n            for j, val in enumerate(row):\n                \n                # we dont need to do anything if we encounter a land\n                if val: continue\n                \n                neighbours = set()\n                res = 0\n                \n                # \n                for x,y in [(i-1, j),(i+1, j),(i, j+1),(i, j-1)]:\n                    # outside of grid check\n                    if not (0 <= x < m and 0 <= y < n): continue\n                        \n                    # checking unique neighbours by adding the parent to the set\n                    # here we dont care if the neighbour is water as its rank is 0 so it contributes nothing\n                    idx = x*m+y\n                    neighbours.add(find(idx))\n                \n                # Once we have all unique neighbours, just add their ranks\n                for idx in neighbours:\n                    res += rank[idx]\n                \n                # res + 1 because we convert the current cell (i,j) to land too\n                ans = max(ans, res+1)\n        \n        return ans\n```\n\nTC: O(n^2*alpha(n)) where alpha is inverse ackerman function\nSC: O(n^2)\n\nHappy to help if anyone has any questions
['Union Find', 'Graph', 'Python']