Leetcode patterns — BFS

After finished 1000 medium level problems. write down the patterns i have learned .

Continue with Previous article . here is another classic algorithm — BFS

In this article i will list all the high ranking problems to explain the classic pattern of BFS leetcode problems ,again, you do not have to solve all the problems, solve the high ranking problems first, focus on learning the patterns and ideas behind the problem itself.

Also , not all patterns could be useful in our day to day work (linklist, bitmask, math, etc) , if just for fun, still can solve other issues later on.

Lets start .

Core idea

def bfs():
    q = [start_nodes]
    while q:
        nexts = []
        while q:
            n = q.pop(0)
            result= do_something(n)
            nexts.extend(next_level_nodes(n))
        q = nexts
     return result

Similar to DFS. the purpose is search . difference is DFS during search wants to go as deep as possible; BFS wants to collect the accessible nodes as wide as possible. maintein a queue is being processed , during each processing , get the next neightbor(or child) nodes .

With above 3 pattern, there are 3 sub patterns, differentiate by searching data structure : Tree, metrix, key-value

BFS with Tree

Start from root, process the nodes level by level. keep the children into queue for next time processing .

def bfs(root):
    q= [root]
    res=[]
    res.append([root.val])
    while q :
        child=[]
        while q:
            n = q.pop(0)
            # do something to current
            if n.children:
                child.extend(n.children)
        if child:
            # do something to children
        q=child
    return res

Sample

429. N-ary Tree Level Order Traversal

Goal : Find every level children and add to result . This is classic BFS model . Though process is simple, start from root, collect every level children, add every level nodes into result .

def levelOrder(self, root: 'Node') -> List[List[int]]:
    if not root:
        return []
    q= [root]
    res=[]
    res.append([root.val])
    while q :
        child=[]
        while q:
            n = q.pop(0)
            if n.children:
                child.extend(n.children)
        if child:
            res.append([x.val for x in child])
        q=child
    return res

Another sample

623. Add One Row to Tree

Thought process: start from root node , track the depth ,once reach the depth , insert row of values . Need handle 3 Case : insert at 1st row, insert at middle, insert at last row.

My Submittion

def addOneRow(self, root: TreeNode, val: int, depth: int) -> TreeNode:
    """
        Case1 : insert at root 
        Case2 : insert at last row
        Case3 : insert betwwn first and last row
    """
    if not root:
        return []
    
    if depth == 1:              # Case1
        return TreeNode(val, root)
    q = [root]
    last_row = []
    d=1
    def insert(n, val):
        left, right = n.left, n.right #original left and right
        n.left = TreeNode(val, left=left) #left=new_node, new_node'left = original left
        n.right = TreeNode(val, right=right)#right=new_node, new_node'right = original right
        return n
    while q:
        if d == depth-1:        # Case3
            for n in q:
                n=insert(n, val)
            return root
        else:
            child = []
            while q:
                n = q.pop(0)
                if n.left:
                    child.append(n.left)
                if n.right:
                    child.append(n.right)
            q = child
            if q:
                last_row = q
        d+=1
    for n in last_row:          # Case2
        n=insert(n, val)
    return root

Other high ranking Tree BFS problems :

919. Complete Binary Tree Inserter

958. Check Completeness of a Binary Tree

102. Binary Tree Level Order Traversal

103. Binary Tree Zigzag Level Order Traversal

107. Binary Tree Level Order Traversal II

199. Binary Tree Right Side View

116. Populating Next Right Pointers in Each Node

513. Find Bottom Left Tree Value

515. Find Largest Value in Each Tree Row

BFS with metrix

Similar idea. difference is that input data structure is metrix . so the “next level” nodes is not children, is connected (left, right, up, down) cells .

994. Rotting Oranges

Thought process: start with rotten oranges . collect neighbor fresh oranges, update state in metrix value (set to rotten) .

Submission :

def orangesRotting(self, grid: List[List[int]]) -> int:
    # load the rotten into q
    q = []
    row, col = len(grid), len(grid[0])
    for r in range(row):
        for c in range(col):
            if grid[r][c] == 2:
                q.append((r,c))
# find the neighbor oranges which could get rotten in next time
    def get_next(r,c):
        d = [(1,0),(0,1),(-1,0),(0,-1)]
        nonlocal grid, row, col
        res = set()
        for d1 in d:
            r1,c1 = r+d1[0], c+d1[1]
            if r1 < 0 or c1 < 0 or r1 == row or c1 == col or grid[r1][c1] != 1:
                continue
            res.add((r1,c1))
        return res
    # BFS rotten the next
    res = 0
    while q:
        nexts = set()
        for r,c in q:
            grid[r][c]=2
        while q:
            r,c = q.pop()
            nexts|=get_next(r,c)
        q = nexts
        if not q: # handle last day
            break
        res+=1
    # all must be rotten then consider success
    for r in range(row):
        for c in range(col):
            if grid[r][c] == 1:
                return -1
    return res

Other high ranking metrix BFS problems :

417. Pacific Atlantic Water Flow (2 times BFS)

542. 01 Matrix

BFS with key-value mapping

433. Minimum Genetic Mutation

Similar idea, the “next nodes” need based on “bank”

Last

That’s all .I believe you grabbed the idea of BFS .

Leetcode is fun and challenging, definally improved programming thinking. it’s worth to add to your weekly routine if you are developer and wants start competitive.

Thanks for reading, happy leetcoding !