Review: Graph Problems

// https://code.dennyzhang.com/as-far-from-land-as-possible
// ...
    for len(queue) > 0 {
        nexts := [][]int{}
        for _, node := range queue {
            i, j := node[0], node[1]
            for _, offset := range [][]int{[]int{1, 0}, []int{-1, 0},
                                           []int{0, 1}, []int{0, -1}} {
                i2, j2 := i+offset[0], j+offset[1]
                if i2<0 || i2>=len(grid) || 
                        j2<0 || j2>=len(grid[0]) || grid[i2][j2] == 1 {
                    continue
                }
                grid[i2][j2] = 1
                nexts = append(nexts, []int{i2, j2})
            }
        }
        level++
        queue = nexts
    }

• Move in 9 directions

// https://code.dennyzhang.com/queens-that-can-attack-the-king
// ...
    i, j := king[0], king[1]
    for x:=-1; x<=1; x++ {
        for y:=-1; y<=1; y++ {
            if x==0 && y==0 {
                continue
            }
            // keep searching this direction
            i2, j2 := i+x, j+y
            for i2>=0 && i2<8 && j2>=0 && j2<8 {
                if m[[2]int{i2,j2}] {
                    res = append(res, []int{i2, j2})
                    break
                }
                i2, j2 = i2+x, j2+y
            }
        }
    }

Questions:

1. Why so many algorithms to find the shortest path? Shouldn’t it be some optimal one(s)?

BFS:

• When to update visited_set? When add or when pop? Employee Importance

BFS:

1. visit all neighbors before visiting neighbors of your neighbors
2. Keep a queue of nodes to visit
3. The performamce may be different if we search from starting point or target point. Perfect Squares

Common graph algorithm problems:

1. Find length of shortest path from node s to all other nodes
2. Search all nodes for a node containing a given value
3. Find shortest path from node s to all other nodes

DFS:

1. visit all neighbors of a neighbor before visiting your other neighbors
2. It doesn’t use queue, but mark nodes as to their status. White(unchecked), Gray(Seen, but not finished), Black(finished)

Key points:

• How to evaluable the time complexity. Normally it’s O(m*n). But how we can convince people with solid argument?

For DFS, if the path is too deep, we might run into stack overflow.

The most impressive problems to me:

• Perfect Squares
• Island Perimeter
• Swim in Rising Water

• CheatSheet: Leetcode For Code Interview

See all grap problems: #graph

• Review: Graph Problems
• LintCode: Social Network
• LintCode: Sliding Puzzle III
• LintCode: Island City
• Leetcode: Word Search
• Leetcode: Word Ladder II
• Leetcode: Word Ladder
• Leetcode: The Maze II
• Leetcode: Surrounded Regions
• Leetcode: Shortest Bridge
• Leetcode: Redundant Connection II
• Leetcode: Redundant Connection
• Leetcode: Reconstruct Itinerary
• Leetcode: Queens That Can Attack the King
• Leetcode: Possible Bipartition
• Leetcode: Path With Maximum Minimum Value
• Leetcode: Pacific Atlantic Water Flow
• Leetcode: Number of Islands II
• Leetcode: Number of Islands
• Leetcode: Maximum Level Sum of a Binary Tree
• Leetcode: Max Area of Island
• Leetcode: Island Perimeter
• Leetcode: Is Graph Bipartite?
• Leetcode: Flood Fill
• Leetcode: Find the Celebrity
• Leetcode: Find Eventual Safe States
• Leetcode: Escape a Large Maze
• Leetcode: Employee Importance
• Leetcode: Critical Connections in a Network
• Leetcode: Contain Virus
• Leetcode: Connecting Cities With Minimum Cost
• Leetcode: Coloring A Border
• Leetcode: Clone Graph
• Leetcode: Bricks Falling When Hit
• Leetcode: As Far from Land as Possible
• Leetcode: All Paths from Source Lead to Destination
• Leetcode: 01 Matrix

See more blog_posts.