Multi Source BFS Algorithm Intro

Intro

Multi Source BFS is an extension of Breadth First Search where we start BFS simultaneously from multiple source nodes.

It is commonly used to propagate distance or spread signals from multiple starting points and find shortest distances to all nodes or earliest reach times.

Unlike regular BFS single source, we enqueue all sources initially and expand layer by layer

Graph Requirements

Unweighted or uniformly weighted graph (BFS gives shortest paths in unweighted graphs)
Directed or Undirected
Represented Using:
- Adjacency List
- Adjacency Matrix

Output

Shortest distance from the nearest source node to every other node

Can also track levels or earliest arrival times from any source

Useful for problems like 'spread of infection' or 'fire spread'

Video Animation

Multi Source BFS: ?

Pseudo Code

    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

Time Complexity

Each node is visited at most once Each edge is processed at most once

O(V + E)

Space Complexity

Queue: O(V) Visited Set: O(V) Distance Map: O(V)

O(V)

IRL Use Case

Fire/Contamination Spread Simulation Track earliest time fire or infection reaches each point from multiple starting locations
Network Signal Propagation Spread from multiple routers in a network

994. Rotting Oranges ::2:: - Medium

Topics: Array, Breadth First Search, Matrix

Intro

You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example Input	Output
grid = [[2,1,1],[1,1,0],[0,1,1]]	4
grid = [[2,1,1],[0,1,1],[1,0,1]]	-1
grid = [[0,2]]	0

Constraints:

m == grid.length

n == grid[i].length

1 ≤ m, n ≤ 10

grid[i][j] is 0, 1, or 2.

Abstraction

Given a grid with oranges, return how much time until no fresh oranges remain.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: [Multi Source BFS] Iterative BFS Rotten Multi Source with Global Minutes Overwrite - Graph/something

    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

Solution 2: [Multi Source BFS] Iterative BFS Rotten Multi Source with Level Processing Minutes Trigger - Graph/something

    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

286. Walls and Gates ::2:: - Medium

Topics: Hash Table, Depth First Search, Breadth First Search, Graph

Intro

You are given a (m) x (n 2D) grid initialized with these three possible values: -1 - A water cell that can not be traversed. 0 - A treasure chest. INF - A land cell that can be traversed. We use the integer 2^31 - 1 = 2147483647 to represent INF. Fill each land cell with the distance to its nearest treasure chest. If a land cell cannot reach a treasure chest then the value should remain INF. Assume the grid can only be traversed up, down, left, or right. Modify the grid in-place.

Example Input	Output
look at diagram	look at diagram

Constraints:

m == grid.length

n == grid[i].length

1 ≤ m, n ≤ 100

grid[i][j] is one of [-1, 0, 2147483647]

Abstraction

Given grid, fill each land grid with the distance to the nearest treasure.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: Multi Source BFS - Graph/something

    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)

127. Word Ladder ::3:: - Hard

Topics: Hash Table, String, Breadth First Search

Intro

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that: Every adjacent pair of words differs by a single letter. Every si for 1 ≤ i ≤ k is in wordList. Note that beginWord does not need to be in wordList sk == endWord Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example Input	Output
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]	5
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]	0

Constraints:

1 ≤ beginWord.length ≤ 10

endWord.length == beginWord.length

1 ≤ wordList.length ≤ 5000

wordList[i].length == beginWord.length

beginWord, endWord, and wordList[i] consist of lowercase English letters.

beginWord != endWord

All the words in wordList are unique.

Abstraction

Given a begin word, end word, and transformation dictionary, determine shortest transformation sequence from begin to end.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: [BFS] BFS - Graph/something

    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

Solution 2: [Bi BFS] Bidirectional BFS - Graph/something

    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

LeetCode: Graphs II Multi Source BFS