def multi_source_bfs(graph, sources):

        visited = set(sources)
        distance = {node: 0 for node in sources}  # Distance from nearest source
        queue = deque(sources)

        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    distance[neighbor] = distance[node] + 1
                    queue.append(neighbor)

        return distance

    def orangesRotting(self, grid: List[List[int]]) -> int:
        
        # Multi Source BFS (Time Stored In Queue)
        # Determine minimum minutes required for all fresh oranges to rot

        # Idea:
        # - Start BFS from ALL rotten oranges simultaneously
        # - Each expansion spreads rot to neighbors
        # - Time (minutes) is carried inside queue state

        # BFS Property:
        # First time an orange is visited = earliest minute it rots

        # Edge Case + Setup

        # Empty Check: no time
        if not grid:
            return -1

        # boundaries
        # sc: O(1)
        m, n = len(grid), len(grid[0])

        # Count Fresh Oranges
        fresh = 0

        # Final Elapsed Time
        minutes = 0

        # Iterative Queue Holds: (row, col, minute)
        # sc: O(m*n)
        queue = deque()

        # Multi Source Setup
        # Iterate across all cells
        # tc: O(m*n)
        for r in range(m):
            for c in range(n):

                # Append ALL rotten oranges as BFS roots
                if grid[r][c] == 2:
                    # add rotten orange as (row, col, minute)
                    queue.append((r, c, 0))
                
                # Add to fresh count
                elif grid[r][c] == 1:
                    fresh += 1

        # BFS Traversal:
        # Each poop represents earliest time this cell rots
        # tc: O(m*n) each cell processed once
        while queue:

            # Process Root
            r, c, minutes = queue.popleft()

            # Process Choices:
            # 4 direction spread
            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                nr, nc = r + dr, c + dc

                # Early Prune:
                # valid bounds + fresh orange
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:

                    # Rot orange immediately
                    grid[nr][nc] = 2
                    fresh -= 1
                    
                    # Pass next minute down BFS
                    queue.append((nr, nc, minutes + 1))

        # Final Validation:
        # if fresh oranges remain, they are unreachable
        res = minutes if fresh == 0 else -1

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

    def orangesRotting(self, grid: List[List[int]]) -> int:
        
        # Multi Source BFS (Time Stored In Queue)
        # Determine minimum minutes required for all fresh oranges to rot

        # Idea:
        # - Start BFS from ALL rotten oranges simultaneously
        # - Each expansion spreads rot to neighbors
        # - Time (minutes) is carried inside queue state

        # BFS Property:
        # First time an orange is visited = earliest minute it rots

        # Edge Case + Setup

        # Empty Check: no time
        if not grid:
            return -1

        # boundaries
        # sc: O(1)
        m, n = len(grid), len(grid[0])

        # Count Fresh Oranges
        fresh = 0

        # Final Elapsed Time
        minutes = 0

        # Iterative Queue Holds: (row, col, minute)
        # sc: O(m*n)
        queue = deque()

        # Multi Source Setup
        # Iterate across all cells
        # tc: O(m*n)
        for r in range(m):
            for c in range(n):

                # Append ALL rotten oranges as BFS roots
                if grid[r][c] == 2:
                    # add rotten orange as (row, col, minute)
                    queue.append((r, c, 0))
                
                # Add to fresh count
                elif grid[r][c] == 1:
                    fresh += 1

        # BFS Traversal:
        # Each poop represents earliest time this cell rots
        # tc: O(m*n) each cell processed once
        while queue and fresh > 0:

            # Process Multiple Roots:
            # All sources at this level
            for _ in range(len(queue)):

                # Process current root
                r, c = queue.popleft()

                # Process Choices:
                # 4 direction spread
                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                    nr, nc = r + dr, c + dc

                    # Early Pruning:
                    # Valid bounds and fresh fruit
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:

                        # Rot orange immediately
                        grid[nr][nc] = 2
                        fresh -= 1

                        # Add next rotten source to queue
                        queue.append((nr, nc))

            # Iterate global minutes tick for next source level
            minutes += 1

        # Final Validation:
        # if fresh oranges remain, they are unreachable
        res = minutes if fresh == 0 else -1

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

    def islandsAndTreasure(self, grid: List[List[int]]) -> None:
        if not grid:
            return

        m, n = len(grid), len(grid[0])
        INF = 2147483647
        q = deque()

        # Step 1: Collect all treasure chests (multi-source roots)
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 0:
                    q.append((r, c))

        # Step 2: BFS flood fill
        while q:
            r, c = q.popleft()

            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                nr, nc = r + dr, c + dc

                # Late Candidate Prune: out of bounds or not INF
                if not (0 <= nr < m and 0 <= nc < n):
                    continue
                if grid[nr][nc] != INF:
                    continue

                # Process Root: update distance from nearest treasure
                grid[nr][nc] = grid[r][c] + 1

                # Process Choices: explore neighbor
                q.append((nr, nc))

        # overall: time O(m * n), space O(m * n) (queue worst-case)

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        
        # Problem Goal:
        # - Transform beginWord into endWord by changing one letter at a time
        # - Each intermediate word must exist in wordList
        # - Find the shortest transformation sequence length

        # Graph Interpretation
        # This is a shortest path problem on an implicit graph:
        #   - Nodes => words
        #   - Edges: words differing by one letter

        # Preprocessing:
        # 1. Store all words in a set for O(1) lookups
        # 2. Generate a dictionary mapping intermediate 'patterns' to possible words
        #   Example:
        #       "hot" => "*ot", "h*t", "ho*"
        #   We generate a structure that lets us implicitly explore edges without
        #   building the full graph

        # Set for lookup
        # sc: O(V)
        wordSet = set(wordList)

        # Empty Check: final word does not exist, return 0
        # tc: O(1)
        if endWord not in wordSet:
            return 0

        # length of original word
        # sc: O(1)
        beginWordLen = len(beginWord)

        # Dictionary storing intermediate patterns to find edges between words
        # sc: O(V * L), V = num words, L = length of word
        all_combo_dict = defaultdict(list)


        # Creating Dictionary Pattern Grouping Lookup:
        # tc: O(V * L^2)

        # iterate through all words (all nodes)
        # tc: O(V)
        for word in wordSet:

            # All words are the same length
            # for each letter in current word
            # tc: O(L)
            for i in range(beginWordLen):

                # Create all possible patterns from this current word:
                # Ex: "hot" => "*ot", "h*t", "ho*"
                #     "wow" => "*ow", "w*w", "wo*"
                # string concatenation
                # tc: O(L)
                pattern = word[:i] + "*" + word[i+1:]

                # Each of these patterns represents a grouping used
                # to find edges between words.
                # So "*ot" defines the group between "not" and "hot",
                # so these two words are neighbors
                # tc: O(1)
                all_combo_dict[pattern].append(word)

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

        # Append original word for processing,
        # depth level is 1 as no letters have been swapped
        # tc: O(1)
        queue.append((beginWord, 1))

        # Tracking Visited
        # sc: O(V)
        visited = set()

        # Append original word as visited
        # tc: O(1)
        visited.add(beginWord)

        # BFS Traversal:
        # tc: O(V * L^2)

        # while we still have neighbor groupings to explore
        # tc: O(V)
        while queue:

            # Grab root word
            # tc: O(1)
            current_word, level = queue.popleft()

            # All words are the same length
            # for each letter in every word available
            # tc: O(L)
            for i in range(beginWordLen):

                # Create all possible patterns from this current word:
                # Ex: "hot" => "*ot", "h*t", "ho*"
                #     "wow" => "*ow", "w*w", "wo*"
                # string concatenation
                # tc: O(L)
                pattern = current_word[:i] + "*" + current_word[i+1:]

                # Explore all neighbors that share this specific pattern:
                # "*ot" => ["not", "hot", "got"]
                # tc: O(V)
                for neighbor in all_combo_dict[pattern]:

                    # if neighbor is expected last word, we have finished
                    # tc: O(1)
                    if neighbor == endWord:

                        # extra level to reach last word
                        return level + 1

                    # Ignore visited neighbors to avoid going backwards
                    # tc: O(1)
                    if neighbor not in visited:

                        # Process Root:
                        # mark as visited
                        # tc: O(1)
                        visited.add(neighbor)

                        # append loop to stack to process
                        # tc: O(1)
                        queue.append((neighbor, level + 1))

                # We mark this pattern as visited
                # by removing all words that share the pattern
                # tc: O(1)
                all_combo_dict[pattern] = []

        # If BFS completes without finding endWord, no path exists, return 0 

        # overall: tc O(V * L^2)
        # overall: sc O(V * L)
        return 0

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

        # Problem Goal:
        # - Transform beginWord into endWord by changing one letter at a time
        # - Each intermediate word must exist in wordList
        # - Find the shortest transformation sequence length

        # Graph Interpretation
        # This is a shortest path problem on an implicit graph:
        #   - Nodes => words
        #   - Edges: words differing by one letter

        # Preprocessing:
        # 1. Store all words in a set for O(1) lookups
        # 2. Generate a dictionary mapping intermediate 'patterns' to possible words
        #   Example:
        #       "hot" => "*ot", "h*t", "ho*"
        #   We generate a structure that lets us implicitly explore edges without
        #   building the full graph


        # Set for lookup
        # sc: O(V)
        wordSet = set(wordList)

        # Empty Check: final word does not exist, return 0
        # tc: O(1)
        if endWord not in wordSet:
            return 0

        # length of original word
        # sc: O(1)
        beginWordLen = len(beginWord)

        # Dictionary Mapping Intermediate Patterns:
        # sc: O(n^2)
        all_combo_dict = defaultdict(list)
        
        # iterate through all words (all nodes)
        # tc: O(V)
        for word in wordSet:

            # All words are the same length
            # for each letter in every word available
            # tc: O(beginWordLen)
            for i in range(beginWordLen):

                # Create all possible patterns from this current word:
                # Ex: "hot" => "*ot", "h*t", "ho*"
                #     "wow" => "*ow", "w*w", "wo*"
                pattern = word[:i] + "*" + word[i+1:]

                # Each of these patterns represents a grouping used
                # to find edges between words.
                # So "*ot" defines the group between "not" and "hot",
                # so these two words are neighbors
                all_combo_dict[pattern].append(word)

        # Bidirectional BFS Setup:
        # begin_set expands forward
        # end_set expands backward
        # sc: O(V)
        begin_set = {beginWord}
        end_set = {endWord}
        
        # Track Visited Words
        # sc: O(V)
        visited = set()
        visited.add(beginWord)
        visited.add(endWord)

        # Current BFS Depth:
        # Will increase when either the begin or end set expand
        # sc: O(1)
        level = 1

        # BFS Traversal:
        # Alternate between exploring the begin and end set,
        # explore the smaller of the two each time.
        # Explore while either of the sets have nodes in them
        # tc: O(V)
        while begin_set and end_set:

            # Always expand smaller frontier,
            # ensures minimal total exploration
            if len(begin_set) > len(end_set):

                # swap the sets so that begin_set is always smaller
                begin_set, end_set = end_set, begin_set

            # Store the next level frontier
            # sc: O(V)
            next_level = set()

            # iterate through all words (all nodes) in set
            # tc: O(V)
            for word in begin_set:

            # All words are the same length
            # for each letter in current word
            # tc: O(L)
                for i in range(beginWordLen):

                    # Create all possible patterns from this current word:
                    # Ex: "hot" => "*ot", "h*t", "ho*"
                    #     "wow" => "*ow", "w*w", "wo*"
                    # tc: O(L)
                    pattern = word[:i] + "*" + word[i+1:]

                    # Each of these patterns represents a grouping used
                    # to find edges between words.
                    # So "*ot" defines the group between "not" and "hot",
                    # so these two words are neighbors
                    # So we will explore all neighbors that share this current pattern,
                    # in other words all neighbors who share this jump of one letter difference
                    # tc: O(V) =~ O(1), we can usually ignore this 
                    # as usually len(all_combo_dict[pattern]) << V
                    for neighbor in all_combo_dict[pattern]:

                        # End and begin set have intersected,
                        # found the smallest number of jumps
                        if neighbor in end_set:
                            return level + 1

                        # New neighbor, Explore
                        if neighbor not in visited:

                            # Process Root:
                            # mark as visited
                            visited.add(neighbor)

                            # Append to queue for processing
                            next_level.add(neighbor)

            # Finished processing begin set, overwrite it with the following set
            # for processing
            begin_set = next_level

            # BFS has expanded another level
            level += 1

        # If either being or end set turn out empty before meeting,
        # no path exists, return 0 

        # overall: tc
        # overall: sc
        return 0

    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:

        # Note:
        # Multi-source BFS: instead of starting from ONE source, seed the queue
        # with ALL water cells simultaneously (height 0), then expand outward together
        # 1. Process all water cells -> :
        #    height 0, added to queue as starting frontier
        # 2. Process -> neighbors :
        #    each unvisited neighbor is exactly 1 higher than the cell that reached it first
        # Result: BFS guarantees the FIRST time a cell is reached is via the
        #         SHORTEST path from its nearest water cell -> correct height

        # Dimensions
        m, n = len(isWater), len(isWater[0])

        # height: -1 sentinel means unvisited; water cells get 0, land gets filled in via BFS
        # sc: O(m*n)
        height = [[-1] * n for _ in range(m)]

        # queue: multi-source BFS frontier, seeded with ALL water cells at once
        queue = deque()

        # Seed queue:
        # every water cell starts as height 0, source of its own BFS wave
        for r in range(m):
            for c in range(n):
                if isWater[r][c] == 1:
                    height[r][c] = 0
                    queue.append((r, c))

        # directions: up, down, left, right (4-directional grid movement)
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        # BFS: propagate heights outward level by level from all water cells
        while queue:
            r, c = queue.popleft()

            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                # Early pruning:
                # skip out-of-bounds or already-visited cells
                # (already-visited means a closer water source already claimed it)
                if 0 <= nr < m and 0 <= nc < n and height[nr][nc] == -1:
                    height[nr][nc] = height[r][c] + 1
                    queue.append((nr, nc))

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

    def shortestBridge(self, grid: List[List[int]]) -> int:

        # Idea:
        #    two islands exist in the grid, connected only through water (0s)
        #    step 1: DFS from any land cell finds and marks the entire first
        #    island (flip its cells to 2), seeding a queue with every cell
        #    of that island along the way
        #    step 2: multi-source BFS expands outward from the whole first
        #    island simultaneously, one water ring per level — the first
        #    time a cell adjacent to unflipped land (1) is reached, that
        #    ring count is the minimum number of water cells crossed

        n = len(grid)

        # directions: the 4 neighbor offsets to check per cell (up, down, left, right)
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(x, y, q):

            # Check:
            # mark this land cell as visited/part of the first island,
            # and seed it into the BFS queue as one of many starting points
            grid[x][y] = 2
            q.append((x, y))

            # Check:
            # explore all 4 neighbors, descending into any unvisited land
            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)

        # BFS Multi-Source Queue:
        # every cell belonging to the first island gets added here via DFS,
        # BEFORE the BFS loop below ever starts. This is what makes the next
        # phase multi-source: all of these cells enter the BFS already
        # sitting in the queue together, all treated as distance 0 at once —
        # not as separate single-source runs processed one at a time.
        queue = deque()

        # Check:
        # scan the grid for the first land cell found, DFS from there to
        # mark the entire first island — problem guarantees exactly two
        # islands, so any land cell belongs to one of them
        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

        # Check:
        # multi-source BFS: the queue already holds every cell of the first
        # island as simultaneous starting points. Each pass through the
        # `for _ in range(len(queue))` loop processes one entire frontier —
        # every cell currently in the queue, regardless of which original
        # island-1 cell it traces back to — before `steps` increments.
        # This guarantees the ring that first touches the second island is
        # the globally shortest distance from ANY point on the first island,
        # not just the distance from one arbitrarily chosen source.
        steps = 0
        while queue:
            for _ in range(len(queue)):
                x, y = queue.popleft()

                # Check:
                # examine all 4 neighbors of this cell
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < n:

                        # Check:
                        # neighbor is unflipped land — this is the second
                        # island, shortest bridge found
                        if grid[nx][ny] == 1:
                            return steps

                        # Check:
                        # neighbor is unvisited water, mark visited and
                        # enqueue it to expand this shared frontier further
                        elif grid[nx][ny] == 0:
                            grid[nx][ny] = 2
                            queue.append((nx, ny))
            steps += 1

        # Check:
        # unreachable in practice — problem guarantees exactly two islands,
        # so the second island is always found during the BFS expansion
        
        # overall: tc O(n^2)
        # overall: sc O(n^2)
        return -1