def islandPerimeter(self, grid: List[List[int]]) -> int:
        
        # Problem:
        # Each land cell contributes 4 edges.
        #
        # But:
        # If two land cells are adjacent,
        # they share one edge.
        # That shared edge removes 2 perimeter edges
        # (one from each cell).
        #
        # Therefore:
        # For each land cell:
        #   Start with 4 sides
        #   Subtract 1 for each adjacent land neighbor
        #
        # Since each shared edge is counted twice
        # (once per cell), subtracting per neighbor
        # naturally handles correct perimeter.
        
        
        rows = len(grid)
        cols = len(grid[0])
        
        perimeter = 0
        
        # Iterate through entire grid
        # tc: O(rows * cols)
        for r in range(rows):
            for c in range(cols):
                
                # Only process land cells
                if grid[r][c] == 1:
                    
                    # Each land cell starts with 4 sides
                    perimeter += 4
                    
                    # Check top neighbor
                    if r > 0 and grid[r - 1][c] == 1:
                        perimeter -= 1
                    
                    # Check bottom neighbor
                    if r < rows - 1 and grid[r + 1][c] == 1:
                        perimeter -= 1
                    
                    # Check left neighbor
                    if c > 0 and grid[r][c - 1] == 1:
                        perimeter -= 1
                    
                    # Check right neighbor
                    if c < cols - 1 and grid[r][c + 1] == 1:
                        perimeter -= 1
        
        # overall: tc O(rows * cols)
        # overall: sc O(1)
        return perimeter

    def islandPerimeter(self, grid: List[List[int]]) -> int:
        
        # Note:
        # Each land cell contributes 4 edges to the perimeter.        
        # If a land cell's neighbor is also land, that shared edge
        # is internal to the island and does not belong to the perimeter.
        # For each land cell, count only the sides that face "outward",
        # either off the grid entirely, or into a water cell (0).

        # Directions and grid representation
        rows = len(grid)
        cols = len(grid[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        # Find any starting land cell to initialize the BFS
        start = None
        for r in range(rows):
            for c in range(cols):

                # Found land, save coordinates
                if grid[r][c] == 1:
                    start = (r, c)
                    break
            if start:
                break

        # Total perimeter count
        perimeter = 0

        # Track land we have already visited to avoid 
        # sc: O(n)
        visited = {start}

        # BFS Iterative Queue:
        # holds land cells we have queued to expand
        queue = deque([start])

        while queue:

            # Pop next land cell to process
            r, c = queue.popleft()

            # Examine all 4 neighbors
            for dr, dc in directions:

                # Shifting Coordinates:
                nr, nc = r + dr, c + dc

                # Perimeter Counting:
                # If a neighbor is out of bounds of the grid, is water,
                # or faces outward, then it counts towards the perimeter
                if nr < 0 or nr >= rows or nc < 0 or nc >= cols or grid[nr][nc] == 0:
                    perimeter += 1
                    continue

                # Neighbor Exploring: 
                # If neighbor is unvisited, enqueue it to continue
                if (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc))

        # overall: tc O(r * c)
        # overall: sc O(r * c)
        return perimeter

    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        
        # Note:
        # 1. Use DFS to traverse the graph
        # 2. Use a hashmap to store already cloned nodes
        # 3. For each node, recursively clone its neighbors
        # 4. Return the cloned node corresponding to the input
        
        # Empty Check: no islands, grid is empty
        # tc: O(1)
        if not node:
            return None

        # Deep copy for new list
        # sc: O(n)
        cloned = {}

        # tc O(V + E) visit each node and edge once
        # sc O(V), for hashmap + recursion stack
        def dfs(n) -> Node:

            # Process Root:
            # clone current node
            copy = Node(n.val)

            # Add clone to hashmap
            cloned[n] = copy

            # Process Candidates:
            # recursively clone all neighbors
            for neighbor in n.neighbors:
                
                # Early Prune: only recurse if neighbor not yet cloned
                if neighbor not in cloned:
                    copy.neighbors.append(dfs(neighbor))
                # else just grab neighbor from clone hashmap
                else:
                    copy.neighbors.append(cloned[neighbor])

            # Return:
            # pass back the cloned node
            return copy

        # Initial Call:
        # return new root of cloned graph
        cloneRoot = dfs(node)

        # overall: tc O(V + E) 
        # overall: sc O(V)
        return cloneRoot

    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        
        # Note:
        # 1. Iterative BFS traversal to clone graph nodes
        # 2. Use hashmap to track original -> cloned node
        # 3. Process Root -> start with input node in queue
        # 4. Process Candidates -> clone neighbors iteratively
        # 5. Early Prune -> skip already cloned neighbors
        # 6. Backtrack -> queue ensures all reachable nodes are processed

        # Empty Check: no islands, grid is empty
        # tc: O(1)
        if not node:
            return None

        # Deep copy of root for new list
        # sc: O(n)
        cloned = {node: Node(node.val)}

        # Iterative queue
        # sc: O(V)
        queue = deque()

        # Append Original Root Node
        # tc: O(1)
        queue.append(node)

        # While we still have nodes in original graph
        # tc O(V + E), each node and edge visited once
        # sc O(V), for hashmap + queue
        while queue:

            # Get Bottom Of Queue Node (original root):
            # tc O(1)
            current = queue.popleft()

            # Iterate over node's neighbors
            for neighbor in current.neighbors:

                # Early Prune: only recurse if neighbor not yet cloned
                if neighbor not in cloned:
                    cloned[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)

                # Grab neighbor from clone hashmap
                cloned[current].neighbors.append(cloned[neighbor])

        cloneRoot = cloned[node]

        # overall: tc O(V + E)
        # overall: sc O(V)
        return cloneRoot

    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        
        # Note:
        # 1. Instead of simulating water flow forward (downhill), reverse the process,
        #    start from the oceans and "climb uphill" to neighbors with height >= current.
        # 2. DFS is used for traversal; recursion handles the exploration
        # 3. Each ocean has its own visited set
        # 4. Cells visited in both traversals can reach both oceans
        # 5. Intersection of visited sets gives the answer


        # Empty check
        if not heights:
            return []

        # boundaries
        m, n = len(heights), len(heights[0])

        # seen
        pacific = set()
        atlantic = set()


        def dfs_TravelUphill(r: int, c: int, ocean_visited: set, prev_height: int) -> None:
            
            # Late Prune:
            # ignore cells if they are out of bounds or visited
            # but specifically if they are downhill, as this means they cannot reach the island
            if (r < 0 or r >= m or 
                c < 0 or c >= n or
                (r, c) in ocean_visited or 
                heights[r][c] < prev_height):
                return

            # Process Root:
            # mark cell as ocean_visited
            ocean_visited.add((r, c))

            # Process Candidates:
            # recursively explore neighbors explore 4 directions
            dfs_TravelUphill(r + 1, c, ocean_visited, heights[r][c])
            dfs_TravelUphill(r - 1, c, ocean_visited, heights[r][c])
            dfs_TravelUphill(r, c + 1, ocean_visited, heights[r][c])
            dfs_TravelUphill(r, c - 1, ocean_visited, heights[r][c])

        # Process Roots:
        # start from Pacific and Atlantic edges
        # These are the edge cells adjacent to each ocean from which water can "flow uphill"
        # just collecting outermost edge calls

        for i in range(m):
            # left column
            dfs_TravelUphill(i, 0, pacific, heights[i][0])
            # right column
            dfs_TravelUphill(i, n - 1, atlantic, heights[i][n - 1])
        for j in range(n):
            # top row
            dfs_TravelUphill(0, j, pacific, heights[0][j])
            # bottom row
            dfs_TravelUphill(m - 1, j, atlantic, heights[m - 1][j])

        # Cells reachable to both oceans
        # tc: O(V)
        intersection = list(pacific & atlantic)

        # overall: tc O(m*n)
        # overall: sc O(m*n)
        return intersection

    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        
        # Note:
        # 1. Same reverse flow idea, but BFS is used instead of DFS.
        # 2. BFS avoids recursion depth issues and may be easier to reason about.
        # 3. Initialize queues with Pacific and Atlantic edges separately.
        # 4. Traverse "uphill" from oceans, track visited cells for each.
        # 5. Answer = intersection of both visited sets.

        # Empty check
        if not heights:
            return []

        # boundaries
        m, n = len(heights), len(heights[0])

        # 
        def bfs(starts: List[Tuple[int,int]]) -> set:

            # Visited set for BFS traversal
            ocean_visited = set(starts)

            # Iterative queue
            queue = deque(starts)

            while queue:
                # Process Root:
                # Grab leftmost cell
                r, c = queue.popleft()

                # Process Choices:
                # Recursively explore neighbors
                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                    nr, nc = r + dr, c + dc

                    # Early Prune:
                    # skip if cell is out of bounds or visited
                    # but most importantly uphill as that means
                    if (0 <= nr < m and 
                        0 <= nc < n and 
                        (nr, nc) not in ocean_visited and 
                        heights[nr][nc] >= heights[r][c]):

                        # mark as visited
                        ocean_visited.add((nr, nc))

                        # add neighbor for processing
                        queue.append((nr, nc))
                        
            # Return all visited cells for this ocean
            return ocean_visited

        # Process Roots -> edge cells for each ocean
        # These are the edge cells adjacent to each ocean from which water can "flow uphill"
        # just collecting outermost edge calls

        # pacific_starts = all cells on the top row (0, j) and all cells on the left column (i, 0)
        pacific_starts = []

        # Top row (first row) for Pacific
        for j in range(n):
            pacific_starts.append((0, j))

        # Left column (first column) for Pacific
        for i in range(m):
            pacific_starts.append((i, 0))

        # Atlantic Ocean edge cells
        atlantic_starts = []

        # Bottom row (last row) for Atlantic
        for j in range(n):
            atlantic_starts.append((m - 1, j))

        # Right column (last column) for Atlantic
        for i in range(m):
            atlantic_starts.append((i, n - 1))

        pacific = bfs(pacific_starts)
        atlantic = bfs(atlantic_starts)

        # Cells reachable to both oceans
        # tc: O(V)
        intersection = list(pacific & atlantic)

        # overall: tc O(m*n)
        # overall: sc O(m*n)
        return intersection

    def shortestBridge(self, grid: List[List[int]]) -> int:
        # Dimensions
        n = len(grid)
        
        # Directions for 4-way movement
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        
        # Step 1: DFS to mark the first island
        def dfs(x, y, q):
            grid[x][y] = 2  # mark as visited
            q.append((x, y))  # add to BFS queue
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                    dfs(nx, ny, q)
        
        # Step 1a: Find the first island and mark it
        queue = deque()
        found = False
        for i in range(n):
            if found:
                break
            for j in range(n):
                if grid[i][j] == 1:
                    dfs(i, j, queue)
                    found = True
                    break
        
        # Step 2: BFS to expand from first island to reach second island
        steps = 0
        while queue:
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < n:
                        if grid[nx][ny] == 1:
                            # Reached second island
                            return steps
                        elif grid[nx][ny] == 0:
                            # Expand water cell
                            grid[nx][ny] = 2
                            queue.append((nx, ny))
            steps += 1
        
        return -1  # just in case, though problem guarantees two islands