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
• CheatSheet: Common Code Problems & Follow-ups

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: Web Crawler
• Leetcode: Tree Diameter
• Leetcode: The Maze II

See more blog posts.