DFS Marking Every Islands | Full Explanation + Hints | 99.87% faster
Intuition\nWe can mark all the islands in one full loop. Then we can count all the unique changed indices around an unchanged (zeroes) index one by one and comp
# Intuition\nWe can mark all the islands in one full loop. Then we can count all the unique changed indices around an unchanged (zeroes) index one by one and compare to return the maximum of all.\n\n# Approach\nTreat all these points as separate hints and try the problem again after reading a single point (for best results ;)).\n- We change the index of an island from one to negative of the `currIslands` i.e. if no islands are found then the value of `currIslands` will be `0` and as soon as we come across our first `1`, we will decrement the `currIslands` and change the value of the index to that of `currIslands`. \n- We can mark these through a dfs function and it will return the number of changed indices, which we will store in a list.\n- After that we will traverse the indices having the value `0`, and check their neighbouring four indices for unique islands.\n- We can now calculate the total landmass around the current index (if it were also land) by using the unique neighbouring islands stored landmass value.\n- Compare it with a variable for maximum result and return the final answer.\n\nYou can now try doing the problem, if still in problem, continue reading the code.\n\nPS: Please upvote if you liked my explanation, it encourages me to write more.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n\n- Space complexity: $$O(n^2)$$\n\n# Code\n```\ndef largestIsland(grid: List[List[int]]) -> int:\n    n = len(grid)\n\n    # A dfs function to mark all the connected indices to \n    # the passed index to the value of currIslands and\n    # return the number of connected indices having 1 as its value\n    def dfs(i: int, j: int) -> int:\n        if i < 0 or j < 0 or i >= n or j >= n or grid[i][j] != 1:\n            return 0\n        grid[i][j] = currIsland\n        return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1)\n\n    # counting the number of islands found\n    currIsland = 0\n    # this array stores the landmass of each island\n    islands = [0]\n    # marking and finding the landmasses of all the islands\n    for i in range(n):\n        for j in range(n):\n            if grid[i][j] == 1:\n                currIsland -= 1\n                islands.append(dfs(i, j))\n\n    maxIsland = max(islands)\n    for i in range(n):\n        for j in range(n):\n            if grid[i][j] == 0:\n                # This set checks for all the unique islands \n                # on the neighbouring four square\n                islandsAround = set()\n                if i > 0 and grid[i - 1][j] < 0:\n                    islandsAround.add(grid[i - 1][j])\n                if i < n - 1 and grid[i + 1][j] < 0:\n                    islandsAround.add(grid[i + 1][j])\n                if j > 0 and grid[i][j - 1] < 0:\n                    islandsAround.add(grid[i][j - 1])\n                if j < n - 1 and grid[i][j + 1] < 0:\n                    islandsAround.add(grid[i][j + 1])\n\n                # calculating the total landmass if this\n                # index was to be a landmass by using \n                # previously stored landmasses of all islands\n                totalLandAround = 1\n                for k in islandsAround:\n                    totalLandAround += islands[-k]\n                maxIsland = max(maxIsland, totalLandAround)\n    return maxIsland\n```\n
['Depth-First Search', 'Python3']