Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

Review: DFS Problems

Posted on August 12, 2019July 26, 2020 by braindenny

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



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

Basic Abstractions

Name Summary
dfs avoid duplicate caculations Maintain state array. And update it at the end of dfs LeetCode: Course Schedule
For backtracking in DFS When and what to do backtracking

Scenarios
Code Skeleton
Top Questions

Name Example
In matrix dfs, change cell to impossible value to avoid state hashmap LeetCode: Word Search II
In matrix dfs, when to change and restore cell state?  
  • dfs get results from return value or input parameters
// https://code.dennyzhang.com/android-unlock-patterns
func dfs(pos int, visited []bool, count int, middles [][]int) int {
    // find one path
    if count == 0 {
        return 1
    }
    res := 0
    visited[pos] = true
    for i:=1; i<=9; i++ {
        if !visited[i] {
            // from pos -> to: adjacent or the middle node visited
            if middles[pos][i] == 0|| visited[middles[pos][i]] {
                res += dfs(i, visited, count-1, middles)
            }
        }
    }
    // backtracking
    visited[pos] = false
    return res
}
// https://code.dennyzhang.com/android-unlock-patterns
func dfs(pos int, visited []bool, count int, middles [][]int, res *int) {
    // find one path
    if count == 0 {
        *res += 1
    }
    visited[pos] = true
    for i:=1; i<=9; i++ {
        if !visited[i] {
            // from pos -> to: adjacent or the middle node visited
            if middles[pos][i] == 0|| visited[middles[pos][i]] {
                 dfs(i, visited, count-1, middles, res)
            }
        }
    }
    // backtracking
    visited[pos] = false
}

See all dfs problems: #dfs

  • Review: DFS Problems
  • LintCode: Word Synthesis Problem
  • LintCode: Island City
  • LintCode: Fermat Point Of Graphs
  • LeetCode: Word Search II
  • LeetCode: Word Search
  • LeetCode: Web Crawler
  • LeetCode: Univalued Binary Tree
  • LeetCode: Unique Paths III
  • LeetCode: Two Sum IV – Input is a BST
  • LeetCode: Tree Diameter
  • LeetCode: The Maze II
  • LeetCode: Ternary Expression Parser
  • LeetCode: Symmetric Tree
  • LeetCode: Surrounded Regions
  • LeetCode: Sum of Distances in Tree
  • LeetCode: Smallest String Starting From Leaf
  • LeetCode: Smallest Rectangle Enclosing Black Pixels
  • LeetCode: Shortest Bridge
  • LeetCode: Remove Sub-Folders from the Filesystem
  • LeetCode: Remove Invalid Parentheses
  • LeetCode: Reconstruct Itinerary
  • LeetCode: Pseudo-Palindromic Paths in a Binary Tree
  • LeetCode: Populating Next Right Pointers in Each Node
  • LeetCode: Path Sum
  • LeetCode: Pacific Atlantic Water Flow
  • LeetCode: Number of Islands
  • LeetCode: Number of Distinct Islands II
  • LeetCode: Number of Distinct Islands
  • LeetCode: Number of Closed Islands
  • LeetCode: Nested List Weight Sum
  • LeetCode: Most Stones Removed with Same Row or Column
  • LeetCode: Minimum Time to Collect All Apples in a Tree
  • LeetCode: Minimum Knight Moves
  • LeetCode: Maximum Product of Splitted Binary Tree
  • LeetCode: Maximum Level Sum of a Binary Tree
  • LeetCode: Maximum Depth of N-ary Tree
  • LeetCode: Maximum Average Subtree
  • LeetCode: Max Area of Island
  • LeetCode: Making A Large Island
  • LeetCode: Lowest Common Ancestor of Deepest Leaves
  • LeetCode: Letter Tile Possibilities
  • LeetCode: Kill Process
  • LeetCode: Keys and Rooms
  • LeetCode: Is Graph Bipartite?
  • LeetCode: House Robber III
  • LeetCode: Generalized Abbreviation
  • LeetCode: Flood Fill
  • LeetCode: Find Leaves of Binary Tree
  • LeetCode: Find All The Lonely Nodes
  • LeetCode: Evaluate Division
  • LeetCode: Escape a Large Maze
  • LeetCode: Employee Importance
  • LeetCode: Cousins in Binary Tree
  • LeetCode: Course Schedule II
  • LeetCode: Course Schedule
  • LeetCode: Count Good Nodes in Binary Tree
  • LeetCode: Coloring A Border
  • LeetCode: Clone Graph
  • LeetCode: Binary Tree Right Side View
  • LeetCode: Android Unlock Patterns
  • LeetCode: All Paths From Source to Target
  • LeetCode: All Paths from Source Lead to Destination
  • LeetCode: 01 Matrix

See more blog posts.

linkedin
github
slack

Post Views: 0
Posted in ReviewTagged #dfs, review

Post navigation

LeetCode: Letter Tile Possibilities
LeetCode: Market Analysis II

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.