Making A Large Island | DFS and BFS | Comments | Python
Steps:\n1. Group all sets of 1\'s into "islands" and give them unique names and store their area in a dictionary.\n2. Go back through the grid and find the 0\'s
Steps:\n1. Group all sets of 1\'s into "islands" and give them unique names and store their area in a dictionary.\n2. Go back through the grid and find the 0\'s that are attached to these islands\n3. Iterate through until the largest new "island" is found.\n\n```\nclass Solution:\n    def largestIsland(self, grid: List[List[int]]) -> int:\n        \n        #What I will be doing is grouping the islands by giving them all unique numbers and storing these numbers with their areas in a dictionary.\n        #This function will do the grouping of the islands and find their total areas.\n\t\t\n\t\t\t#x and y are the location in the grid and num will be the "name" of the island, which I will just use as an incrementally increasing set of integers\n\t\t\tdef redefineGrid(x, y, num): \n            if grid[x][y] != 1: #if we hit water we can just return zero as there is no need to access this part of the array.\n                return 0\n            grid[x][y] = num  #Here we will keep track of each mass of 1\'s by naming each island.\n            area = 1\n            if x + 1 < len(grid):\n                area += redefineGrid(x + 1, y, num)\n            if y + 1 < len(grid[0]):\n                area += redefineGrid(x, y + 1, num)\n            if x - 1 >= 0:\n                area += redefineGrid(x - 1, y, num)\n            if y - 1 >= 0:\n                area += redefineGrid(x, y - 1, num)\n            return area\n\n      \n        mem = {}  #mem will be the dictionary.\n        current = 2  #Each group of islands gets its own name. We will ignore 1 to make the entire thing easier to begin with and iterate up as we go.\n        subTotal = 0\n        totalSize = len(grid) * len(grid[0])\n        \n        #Now we iterate through the array looking for islands and adding their names and area values to the dictionary.\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == 1:\n                    subTotal = redefineGrid(i, j, current)\n                    if subTotal >= totalSize - 1: #This is a trivial case where either the entire array is 1\'s or if there is only one 0, in which case, the area is the total\n                        return totalSize\n                    mem[current] = subTotal\n                    current += 1\n\n        #now we will look through the grid once again, this time trying to identify the "water" or 0\'s and try to use them to connect to different islands.\n        #curArray will be used to keep track of which islands are already part of the new landmass so we don\'t double count islands along the way.\n        largest = 0\n        curArray = []\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == 0:\n                  #Setting the stage for the current location by clearing old values.\n                    current = 0\n                    curArray.clear()\n                    if i + 1 < len(grid) and grid[i + 1][j] != 0:\n                        current += mem[grid[i + 1][j]]\n                        curArray.append(grid[i + 1][j])\n                    if i - 1 >= 0 and grid[i - 1][j] != 0 and curArray.count(grid[i - 1][j]) == 0:  #using the array curArray, we keep track of the islands we already counted\n                        current += mem[grid[i - 1][j]]\n                        curArray.append(grid[i - 1][j])\n                    if j + 1 < len(grid[0]) and grid[i][j + 1] != 0 and curArray.count(grid[i][j + 1]) == 0:\n                        current += mem[grid[i][j + 1]]\n                        curArray.append(grid[i][j + 1])\n                    if j - 1 >= 0 and grid[i][j - 1] != 0 and curArray.count(grid[i][j - 1]) == 0:\n                        current += mem[grid[i][j - 1]]\n                        curArray.append(grid[i][j - 1])\n                    #We want to add the current 0 we are looking at, so each current will end up being current + 1\n                    if current + 1 > largest:\n                        largest = current + 1\n        if largest == 0 and totalSize > 0:\n        #in another trivial case where the entire array is 0\'s, we can make a single 1, so we will return 1. Note: the trivial case of a 0-value array is solved below.\n            return 1\n        return largest\n```
['Depth-First Search', 'Python']