public

DFS & BFS, the most used interview questions

BFS & DFS are the most common interview questions, they can solve one same questions with both solution. Let's go! we trained the same question both with DFS & BFS!

2 months ago

Latest Post FSE Emergency Social Network (Carnegie Mellon University Project) by Xiaotian public

BFS & DFS are the most common interview questions, they can solve one same questions with both solution. Let's go!
we trained the same question both with DFS & BFS!

MATRIX LEVEL -- BFS & DFS

733. Flood Fill
  1. BFS
    flood1-grid

Method 1: Do the task first then insert into queue!

import collections
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
    if image[sr][sc] == newColor:
        return image
    
    rows, cols = len(image), len(image[0])
    oldColor = image[sr][sc]
    
    # first do the task! then insert base element
    image[sr][sc] = newColor
    q = deque()
    q.append([sr,sc])
    
    # loop until q cannot go further
    while q:
        i, j = q.popleft()
        
        
        # find all possible direction for this point
        for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
            if 0 <= x < rows and 0 <= y < cols and image[x][y] == oldColor:
                # first do! then insert surronding elements
                image[x][y] = newColor
                q.append([x, y])
    return image

Method 2: insert into queue then do stuff!

import collections
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
    if image[sr][sc] == newColor:
        return image
    
    rows, cols = len(image), len(image[0])
    oldColor = image[sr][sc]
    
    # insert base element first
    q = deque()
    q.append([sr,sc])
    
    # loop until q cannot go further
    while q:
        i, j = q.popleft()

        # do it here!
        image[i][j] = newColor
        
        # find all possible direction for this point
        for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
            if 0 <= x < rows and 0 <= y < cols and image[x][y] == oldColor:
                # insert surrounding elements first!
                q.append([x, y])
    return image
  1. DFS

matrix DFS ALWAYS use recursion, tree DFS can use DFS recursion or stack!

def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        # DFS ALWAYS start with a list of judgements for simplification
        if image[sr][sc] == newColor:
            return image
    
        rows, cols = len(image), len(image[0])
        
        # base and "always" operation
        oldColor = image[sr][sc]
        image[sr][sc] = newColor
        
        # recursion around all surronding (REMEBER To set up stop condition)
        for x, y in (sr, sc + 1), (sr + 1, sc), (sr - 1, sc), (sr, sc - 1):
            if 0 <= x < rows and 0 <= y < cols and image[x][y] == oldColor:
                self.floodFill(image, x, y, newColor)

        return image

200. Number of Islands
  1. DFS
import collections
def numIslands(self, grid: List[List[str]]) -> int:
    
    rows = len(grid)
    cols = len(grid[0])
    count = 0
    
    def bfs(grid, m, n):
        res = 0
        if grid == None: return res

        q = deque()
        q.append((m, n))
        grid[m][n] = "#"
        
        while q:
            curNode = q.popleft()
            
            for x, y in (curNode[0] + 1, curNode[1]), (curNode[0], curNode[1] + 1), (curNode[0] - 1, curNode[1]), (curNode[0], curNode[1] - 1):
                if 0 <= x < rows and 0 <= y < cols and grid[x][y] == "1":
                    grid[x][y] = "#"
                    q.append((x, y))
                    
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == "1":
                bfs(grid, row, col)
                count += 1
    
    return count
  1. BFS
def numIslands(self, grid: List[List[str]]) -> int:
        
        def dfs(grid, i, j):
            if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
                return
            grid[i][j] = '#'  # THE MOST IMPORTANT STEP, VISITED STEP
            dfs(grid, i+1, j)
            dfs(grid, i-1, j)
            dfs(grid, i, j+1)
            dfs(grid, i, j-1)
        
        if not grid:
            return 0

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(grid, i, j)
                    count += 1
        return count
490. The Maze

https://assets.leetcode.com/uploads/2021/03/31/maze1-1-grid.jpg

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

  1. BFS
import collections
    import collections
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        rows = len(maze)
        cols = len(maze[0])
        dir = [1, 0, -1, 0, 1]
        visited = [[0 for _ in range(cols)] for _ in range(rows)]
        q = deque()
        q.append(start)
        visited[start[0]][start[1]] = 1

        while q: 
            cur = q.popleft()
            if cur[0] == destination[0] and cur[1] == destination[1]:
                return True

            for i in range(4):
                newX = cur[0]
                newY = cur[1]
                while 0 <= newX < rows and 0 <= newY < cols and maze[newX][newY] != 1:
                    newX += dir[i]
                    newY += dir[i + 1]
                newX -= dir[i]
                newY -= dir[i + 1]

                if visited[newX][newY]: continue
                q.append([newX, newY])
                visited[newX][newY] = 1

        return False
505. The Maze II

https://assets.leetcode.com/uploads/2021/03/31/maze1-1-grid.jpg

  1. BFS
    import collections
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        rows = len(maze)
        cols = len(maze[0])
        
        dir = [1, 0, -1, 0, 1]
        res = [[float('inf') for _ in range(cols)] for _ in range(rows)]
        q = deque()
        q.append([start[0], start[1], 0])

        while q: 
            cur = q.popleft()
            if cur[2] >= res[cur[0]][cur[1]]:
                continue
            res[cur[0]][cur[1]] = cur[2]
            
            for i in range(4):
                newX = cur[0]
                newY = cur[1]
                path = cur[2]
                while 0 <= newX < rows and 0 <= newY < cols and maze[newX][newY] == 0:
                    newX += dir[i]
                    newY += dir[i + 1]
                    path += 1
                newX -= dir[i]
                newY -= dir[i + 1]
                path -= 1
                q.append([newX, newY, path])

        return -1 if res[destination[0]][destination[1]] == float('inf') else res[destination[0]][destination[1]]

ARRAY LEVEL -- BFS & DFS

78. Subsets

Solution 1

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

def subsets(self, nums: List[int]) -> List[List[int]]:
    def backtract(sublist, templist, nums, start):
        sublist.append(templist[:])
        for i in range(start, len(nums)):
            templist.append(nums[i])
            backtract(sublist, templist, nums, i + 1)
            templist.pop()
        return sublist
            
    sublist = []
    nums.sort()
    return backtract(sublist, [], nums, 0)

Solution 2

def subsets(self, nums):
    result = [[]]
    for num in nums:
        result += [i + [num] for i in result]
    return result
90. Subsets II

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    def backtract(sublist, templist, nums, start):
        sublist.append(templist[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            templist.append(nums[i])
            backtract(sublist, templist, nums, i + 1)
            templist.pop()
        return sublist
            
    sublist = []
    nums.sort()
    return backtract(sublist, [], nums, 0)
46. Permutations

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

def backtract(self, reslist, templist, nums) -> List[List[int]]:
        if len(templist) == len(nums):
            reslist.append(templist[:])
        else:
            for i in range(len(nums)):
                if nums[i] in templist:
                    continue
                templist.append(nums[i])
                self.backtract(reslist, templist, nums)
                templist.pop()
        return reslist
    
def permute(self, nums: List[int]) -> List[List[int]]:
    reslist = []
    nums.sort()
    return self.backtract(reslist, [], nums)
47. Permutations II

Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]

def backtract(self, reslist, templist, nums, used) -> List[List[int]]:
        if len(templist) == len(nums):
            reslist.append(templist[:])
        else:
            for i in range(len(nums)):
                if used[i] == 1 or i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue
                used[i] = 1
                templist.append(nums[i])
                self.backtract(reslist, templist, nums, used)
                used[i] = 0
                templist.pop()
        return reslist
    
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    reslist = []
    boolean = [0 for _ in range(len(nums))]
    nums.sort()
    return self.backtract(reslist, [], nums, boolean)
39. Combination Sum

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

def backtrack(self, reslist, templist, nums, remain, start) -> List[List[int]]:
        if remain < 0: 
            return
        elif remain == 0:
            reslist.append(templist[:])
        else:
            for i in range(start, len(nums)):
                templist.append(nums[i])
                self.backtrack(reslist, templist, nums, remain - nums[i], i)
                templist.pop()
        return reslist
    
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        reslist = []
        candidates.sort()
        return self.backtrack(reslist, [], candidates, target, 0)
40. Combination Sum II

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

def backtrack(self, reslist, templist, nums, remain, start) -> List[List[int]]:
        if remain < 0: 
            return
        elif remain == 0:
            reslist.append(templist[:])
        else:
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                templist.append(nums[i])
                self.backtrack(reslist, templist, nums, remain - nums[i], i + 1)
                templist.pop()
        return reslist
    
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    reslist = []
    candidates.sort()
    return self.backtrack(reslist, [], candidates, target, 0)
        
131. Palindrome Partitioning

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

https://leetcode.com/problems/palindrome-partitioning/Figures/131/time_complexity.png

    def isPalindrome(self, s, start, end) -> bool:
        temp = s[start:end + 1]
        return temp == temp[::-1]
    
    def backtrack(self, reslist, templist, s, start) -> List[List[int]]:
        if start == len(s):
            reslist.append(templist[:])
        else:
            for i in range(start, len(s)):
                if self.isPalindrome(s, start, i):
                    templist.append(s[start: i + 1])
                    self.backtrack(reslist, templist, s, i + 1)
                    templist.pop()
                    
        return reslist
    
    def partition(self, s: str) -> List[List[str]]:
        reslist = []
        return self.backtrack(reslist, [], s, 0)
  1. Binary Tree Level Order Traversal

Why this is wrong?

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    import collections
    if root == None: return res
    
    res = []
    q = deque()
    q.append(root)
    
    while q:
        temp = q.popleft()
        res.append(temp.val)
        
        if temp.left != None:
            q.append(temp.left)
            
        if temp.right != None:
            q.append(temp.right)
    
    return res

Use your level

    import collections
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        res = []
        if root == None: return res
        
        q = deque()
        q.append(root)
        
        while q:
            
            # SIZE! OF! THE! QUEUE!
            size = len(q)
            
            curLevel = []
            for i in range(size):
                curNode = q.popleft()
                curLevel.append(curNode.val)
                
                if curNode.left != None:
                    q.append(curNode.left)

                if curNode.right != None:
                    q.append(curNode.right)
            
            res.append(curLevel)
        return res

BINARY TREE LEVEL -- BFS & DFS

  1. Binary Tree Zigzag Level Order Traversal
import collections
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    res = []

    if root == None: return res
    
    q = deque()
    q.append(root)
    
    counter = 0
    while q:
        curLevel = []
        for i in range(len(q)):
            curNode = q.popleft()
            curLevel.append(curNode.val)
            
            if curNode.left:
                q.append(curNode.left)

            if curNode.right:
                q.append(curNode.right)
        
        if counter % 2 == 0:
            res.append(curLevel)
        else:
            res.append(curLevel[::-1])
            
        counter += 1
        
    return res

  1. Validate Binary Search Tree

Template of inorder traversal

def isValidBST(self, root: Optional[TreeNode]) -> bool:
    if root == None: return True
    stack = []
    ls = []
    
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
            
        root = stack.pop()
        
        # condition here
        root = stack.pop()
        ls.append(root.val)
        
        root = root.right
        
    return ls

Inorder traversal

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root == None: return True
        
        stack = []
        pre = None
        
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
                
            root = stack.pop()
            
            # greater or equal than!
            if pre and pre.val >= root.val:
                return False
            
            pre = root
            root = root.right
            
        return True

dfs


    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def isValidBST(root, minValue, maxValue):
            if root == None: return True

            if root.val >= maxValue or root.val <= minValue:
                return False

            return isValidBST(root.left, minValue, root.val) and isValidBST(root.right, root.val, maxValue)

        return isValidBST(root, -sys.maxsize, sys.maxsize)  
  1. Kth Smallest Element in a BST
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
    if root == None: return -1
    
    stack = []
    
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
            
        root = stack.pop()
        
        if k == 1: return root.val
        k -= 1
        
        root = root.right
        
    return -1

  1. Flatten Binary Tree to Linked List
def flatten(self, root: Optional[TreeNode]) -> None:
        def dfs(root):
            if root == None: return None
            leftLast = dfs(root.left)
            rightLast = dfs(root.right)
            
            if leftLast:
                
                ############
                leftLast.right = root.right
                root.right = root.left
                root.left = None
                ############
                
            if rightLast != None:
                return rightLast
            if leftLast != None:
                return leftLast
            
            return root
    
        dfs(root)
  1. Binary Tree Right Side View

Why this is wrong?

def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    res = []
    if root == None: return res
    
    q = collections.deque()
    q.append(root)
    res.append(root.val)
    while q:
        for i in range(len(q)):
            curNode = q.popleft()
            
            if i == len(q) - 1:
                res.append(curNode.val)
            if curNode.left:
                q.append(curNode.left)
            if curNode.right:
                q.append(curNode.right)

    return res

It should be:

def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    res = []
    if root == None: return res
    
    q = collections.deque()
    q.append(root)
    while q:
        size = len(q)
        for i in range(size):
            curNode = q.popleft()
            
            if curNode.left:
                q.append(curNode.left)
                
            if curNode.right:
                q.append(curNode.right)
                
            if i == size - 1:
                res.append(curNode.val)
    return res

dfs

def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    def dfs(root, depth, res):
        if root == None: return
        
        if depth == len(res):
            res.append(root.val)
            
        dfs(root.right, depth + 1, res)
        dfs(root.left, depth + 1, res)
    
    res = []
    dfs(root, 0, res)
    return res
Xiaotian

Published 2 months ago