Untitled

# I DID THIS ENTIRE PROBLEM ON MY OWN WITHOUT LOOKING ANYTHING UP WOOO
# Aug 19, 2025

import random

class Solution:
    def __init__(self):
        self.sizeMap = dict() # <(row, col), size>
        # we keep random IDs per island so we don't double-count
        self.idMap = dict() # <(row, col), size>
        self.currIslandSize = 0
        self.currIslandNodes = [] # (row, col)
        self.allSizes = set()
        self.bridgeFound = False

    def largestIsland(self, grid: List[List[int]]) -> int:
        
        # cover edge cases
        if len(grid) == 0:
            return 0
        if len(grid) == 1:
            return 1
        
        # add the sizes of all adjacent islands
        def getBridgedSize(row, col):
            bridgedSize = 1
            currIDs = []
            
            # up
            if row > 0 and grid[row-1][col] == 1 and self.idMap[(row-1, col)] not in currIDs:
                bridgedSize += self.sizeMap[(row-1, col)]
                currIDs.append(self.idMap[(row-1, col)])

            # right
            if col < len(grid)-1 and grid[row][col+1] == 1 and self.idMap[(row, col+1)] not in currIDs:
                bridgedSize += self.sizeMap[(row, col+1)]
                currIDs.append(self.idMap[(row, col+1)])

            # down
            if row < len(grid)-1 and grid[row+1][col] == 1 and self.idMap[(row+1, col)] not in currIDs:
                bridgedSize += self.sizeMap[(row+1, col)]
                currIDs.append(self.idMap[(row+1, col)])

            # left
            if col > 0 and grid[row][col-1] == 1 and self.idMap[(row, col-1)] not in currIDs:
                bridgedSize += self.sizeMap[(row, col-1)]
                currIDs.append(self.idMap[(row, col-1)])

            return bridgedSize
        
        def traverse(row, col):
            # successfully identified a currIsland node
            self.currIslandSize += 1
            self.currIslandNodes.append((row, col))
            self.sizeMap[(row, col)] = 1
            self.idMap[(row, col)] = 1

            # traverse if in-bounds AND is 1 AND not checked
            # up
            if row > 0 and grid[row-1][col] == 1 and (row-1, col) not in self.sizeMap:
                traverse(row-1, col)

            # right
            if col < len(grid)-1 and grid[row][col+1] == 1 and (row, col+1) not in self.sizeMap:
                traverse(row, col+1)

            # down
            if row < len(grid)-1 and grid[row+1][col] == 1 and (row+1, col) not in self.sizeMap:
                traverse(row+1, col)

            # left
            if col > 0 and grid[row][col-1] == 1 and (row, col-1) not in self.sizeMap:
                traverse(row, col-1)

            return

        # check each node to find existing islands
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1 and (i, j) not in self.sizeMap:
                    self.currIslandSize = 0
                    self.currIslandNodes = []
                    traverse(i, j)

                    randomID = random.random()

                    # encode currIsland size into each island node
                    for n in self.currIslandNodes:
                        self.sizeMap[n] = self.currIslandSize
                        self.idMap[n] = randomID

                    # encode size in case we need it
                    self.allSizes.add(self.currIslandSize)

        currLargestBridgedSize = 1

        # scan the whole grid for islandConnector nodes
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    self.bridgeFound = True
                    size = getBridgedSize(i, j)
                    # see if it's greater than largest total so far
                    if size > currLargestBridgedSize:
                        currLargestBridgedSize = size

        # edge case: no 0 nodes found, we instead just want the largest island
        if not self.bridgeFound:
            return sorted(self.allSizes)[len(self.allSizes)-1]

        return currLargestBridgedSize