Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

Review: BFS Problems

Posted on February 8, 2018July 26, 2020 by braindenny

BFS is extremely useful. You may not imagine.

Here we try to compile a list of inspiring BFS problems.



Name Comment
bfs: level=0 vs level=1  
bfs first level/normal level/last level last level would be empty
bfs with priority queue  
When to collect result: before enque vs after deque  
Understand the physical meaning of level LeetCode: As Far from Land as Possible
If original grid can be changed, visited bool array might be optional LeetCode: As Far from Land as Possible
Some BFS may not necessarily need visited hashmap: say topological BFS sort LeetCode: Course Schedule II
BFS traverse nodes with same value of different positions LeetCode: Jump Game IV

Code Skeleton

// Blog link: https://code.dennyzhang.com/maximum-level-sum-of-a-binary-tree
// Basic Ideas: bfs
//
// Complexity: Time O(n), Space O(n)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxLevelSum(root *TreeNode) int {
    level, maxSum, res := 1, -1<<31, 0

    queue := []*TreeNode{root}
    for len(queue) != 0 {
        l := []*TreeNode{}
        sum := 0
        for _, node := range queue {
            sum += node.Val
            if node.Left != nil {
                l = append(l, node.Left)
            }
            if node.Right != nil {
                l = append(l, node.Right)
            }
        }
        if sum > maxSum {
            maxSum, res = sum, level
        }
        queue = l
        level++
    }
    return res
}
  1. BFS in string: Letter Case Permutation
  2. Distance with power: Cheapest Flights Within K Stops
  3. Revisit seen nodes: Knight Probability in Chessboard
  4. BFS with heap: Movie Network
  5. For seen set use array, instead of a set: Is Graph Bipartite
  6. Scan from target to original: Reach a Number
  7. BFS with memoization: Target Sum

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups

See all bfs problems: #bfs

  • Review: BFS Problems
  • LintCode: Social Network
  • LintCode: Police Distance
  • Lintcode: Movie Network
  • LintCode: Maximum Association Set
  • LintCode: Island City
  • LintCode: Deliver The Message
  • LeetCode: Word Ladder II
  • LeetCode: Word Ladder
  • LeetCode: Web Crawler
  • LeetCode: Walls and Gates
  • LeetCode: Two Sum IV – Input is a BST
  • LeetCode: Tree Diameter
  • LeetCode: Trapping Rain Water II
  • LeetCode: The Maze III
  • LeetCode: The Maze II
  • LeetCode: The Maze
  • LeetCode: Symmetric Tree
  • LeetCode: Sliding Puzzle
  • LeetCode: Similar String Groups
  • LeetCode: Shortest Path with Alternating Colors
  • LeetCode: Shortest Path in Binary Matrix
  • LeetCode: Shortest Path in a Grid with Obstacles Elimination
  • LeetCode: Shortest Distance to a Character
  • LeetCode: Shortest Distance from All Buildings
  • LeetCode: Shortest Bridge
  • LeetCode: Serialize and Deserialize N-ary Tree
  • LeetCode: Sequence Reconstruction
  • LeetCode: Rotting Oranges
  • LeetCode: Remove Invalid Parentheses
  • LeetCode: Push Dominoes
  • LeetCode: Print Binary Tree
  • LeetCode: Path Sum
  • LeetCode: Parallel Courses
  • LeetCode: Pacific Atlantic Water Flow
  • LeetCode: Output Contest Matches
  • LeetCode: Out of Boundary Paths
  • LeetCode: Open the Lock
  • LeetCode: Numbers With Same Consecutive Differences
  • LeetCode: Number of Ways of Cutting a Pizza
  • LeetCode: Network Delay Time
  • LeetCode: N-ary Tree Level Order Traversal
  • LeetCode: Minimum Time to Collect All Apples in a Tree
  • LeetCode: Minimum Moves to Move a Box to Their Target Location
  • LeetCode: Minimum Knight Moves
  • LeetCode: Minimum Height Trees
  • LeetCode: Minimum Genetic Mutation
  • LeetCode: Maximum Score Words Formed by Letters
  • LeetCode: Maximum Level Sum of a Binary Tree
  • LeetCode: Maximum Depth of N-ary Tree
  • LeetCode: Matrix Cells in Distance Order
  • LeetCode: Letter Case Permutation
  • LeetCode: Knight Probability in Chessboard
  • LeetCode: Knight Dialer
  • LeetCode: Kill Process
  • LeetCode: Keys and Rooms
  • LeetCode: Jump Game IV
  • LeetCode: Jump Game III
  • LeetCode: Is Graph Bipartite?
  • LeetCode: Graph Valid Tree
  • LeetCode: Generalized Abbreviation
  • LeetCode: Frog Jump
  • LeetCode: Find the Kth Smallest Sum of a Matrix With Sorted Rows
  • LeetCode: Find Leaves of Binary Tree
  • LeetCode: Find Bottom Left Tree Value
  • LeetCode: Escape a Large Maze
  • LeetCode: Employee Importance
  • LeetCode: Directed Graph Loop
  • LeetCode: Diagonal Traverse II
  • LeetCode: Cousins in Binary Tree
  • LeetCode: Course Schedule II
  • LeetCode: Course Schedule
  • LeetCode: Coin Change
  • LeetCode: Closest Leaf in a Binary Tree
  • LeetCode: Cheapest Flights Within K Stops
  • LeetCode: Champagne Tower
  • LeetCode: Bus Routes
  • LeetCode: Binary Tree Zigzag Level Order Traversal
  • LeetCode: Binary Tree Right Side View
  • LeetCode: Binary Tree Level Order Traversal II
  • LeetCode: Binary Tree Level Order Traversal
  • LeetCode: Average of Levels in Binary Tree
  • LeetCode: All Paths from Source Lead to Destination
  • LeetCode: All Nodes Distance K in Binary Tree
  • LeetCode: 01 Matrix

See more blog posts.

linkedin
github
slack

Post Views: 8
Posted in ReviewTagged #bfs, review

Post navigation

Join Our Slack Group
Review Of Code Problems & Follow-ups

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.