Advanced Graphs
Once edges have weights (distance, cost, time) plain BFS is not enough. Here you learn shortest paths with a heap (Dijkstra), cheapest ways to connect everything (minimum spanning tree) and ordering with dependencies.
After this topic: You can pick between BFS, Dijkstra, Bellman-Ford style relaxation and a spanning-tree algorithm, and implement each with a heap.
Do these first: Graphs
Step 1 · Read the lesson
Weighted graphs: cheapest paths with a heap, cheapest ways to connect everything, and ordering by rules.
Step 2 · Solve the problems in order
Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.
- 1.Reconstruct ItineraryHard
You must use every ticket exactly once, and pick the smallest airport first. Which kind of path is that?
Hierholzer's algorithm: sort destinations, DFS taking the smallest unused edge, append the airport after its edges are exhausted, then reverse the result.
Target: O(E log E) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func findItinerary(tickets [][]string) []stringTested with go test. Try it yourself first, then compare. It is explained step by step on the Advanced Graphs · Dijkstra & Spanning Trees lesson page.
// FindItinerary: use every ticket once, smallest airport name first (Hierholzer's algorithm). func FindItinerary(tickets [][]string) []string { adj := map[string][]string{} for _, t := range tickets { adj[t[0]] = append(adj[t[0]], t[1]) } for from := range adj { sort.Sort(sort.Reverse(sort.StringSlice(adj[from]))) // reversed so popping the end gives the smallest } var route []string var visit func(string) visit = func(airport string) { for len(adj[airport]) > 0 { next := adj[airport][len(adj[airport])-1] adj[airport] = adj[airport][:len(adj[airport])-1] visit(next) } route = append(route, airport) // added only once stuck: dead ends end up at the back } visit("JFK") for i, j := 0, len(route)-1; i < j; i, j = i+1, j-1 { route[i], route[j] = route[j], route[i] } return route } - 2.Min Cost to Connect All PointsMedium
Connect everything with the least total wire — and with no cycles. That is a famous structure.
Minimum spanning tree: Prim's with a heap (start anywhere, repeatedly add the cheapest edge to a new point) or Kruskal's with union-find.
Target: O(n² log n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func minCostConnectPoints(points [][]int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Advanced Graphs · Dijkstra & Spanning Trees lesson page.
// MinCostConnectPoints: minimum spanning tree with Prim's algorithm. // Grow one tree: repeatedly attach the point that is cheapest to reach from the tree. func MinCostConnectPoints(points [][]int) int { n := len(points) dist := make([]int, n) // cheapest known cost to attach each point to the tree for i := range dist { dist[i] = math.MaxInt } inTree := make([]bool, n) dist[0] = 0 total := 0 for range n { best := -1 for i := 0; i < n; i++ { if !inTree[i] && (best == -1 || dist[i] < dist[best]) { best = i } } inTree[best] = true total += dist[best] for i := 0; i < n; i++ { if !inTree[i] { d := abs(points[best][0]-points[i][0]) + abs(points[best][1]-points[i][1]) dist[i] = min(dist[i], d) } } } return total } func abs(x int) int { if x < 0 { return -x } return x } - 3.Network Delay TimeMedium
The time for the signal to reach a node is the shortest weighted path from the source.
Dijkstra with a min-heap of (distance, node); answer is the largest shortest distance, or −1 if some node is unreachable.
Target: O(E log V) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func networkDelayTime(times [][]int, n int, k int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Advanced Graphs · Dijkstra & Spanning Trees lesson page.
// NetworkDelayTime: times[i] = {from, to, weight}, nodes are 1..n. // The signal reaches everyone when it reaches the farthest node. func NetworkDelayTime(times [][]int, n, k int) int { graph := make([][]Edge, n+1) for _, t := range times { graph[t[0]] = append(graph[t[0]], Edge{t[1], t[2]}) } dist := Dijkstra(graph, k) worst := 0 for node := 1; node <= n; node++ { if dist[node] == math.MaxInt { return -1 } worst = max(worst, dist[node]) } return worst } - 4.Swim in Rising WaterHard
The cost of a path is the highest cell on it, not the sum. You want the path whose maximum is smallest.
Dijkstra-style: heap ordered by the max height seen so far; pop the cheapest cell and push its neighbours with max(current, neighbour). (Binary search + BFS also works.)
Target: O(n² log n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func swimInWater(grid [][]int) intTested with go test. Try it yourself first, then compare.
// SwimInWater: you can cross a cell once the water level reaches its height, so a path costs the HIGHEST cell // on it. Dijkstra with "max" instead of "+": always expand the cell whose path-maximum is smallest. func SwimInWater(grid [][]int) int { n := len(grid) seen := make([][]bool, n) for i := range seen { seen[i] = make([]bool, n) } h := &cellHeap{{grid[0][0], 0, 0}} // {path maximum, row, col} for h.Len() > 0 { cur := heap.Pop(h).([3]int) level, r, c := cur[0], cur[1], cur[2] if seen[r][c] { continue } seen[r][c] = true if r == n-1 && c == n-1 { return level } for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} { nr, nc := r+d[0], c+d[1] if nr >= 0 && nc >= 0 && nr < n && nc < n && !seen[nr][nc] { heap.Push(h, [3]int{max(level, grid[nr][nc]), nr, nc}) } } } return -1 } type cellHeap [][3]int func (h cellHeap) Len() int { return len(h) } func (h cellHeap) Less(i, j int) bool { return h[i][0] < h[j][0] } func (h cellHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *cellHeap) Push(x any) { *h = append(*h, x.([3]int)) } func (h *cellHeap) Pop() any { old := *h x := old[len(old)-1] *h = old[:len(old)-1] return x } - 5.Alien DictionaryHard
Compare adjacent words: the first different letter tells you one ordering rule between two letters.
Build edges from adjacent word pairs (watch for the invalid "abc" before "ab" case), then topologically sort; a cycle means no valid order.
Target: O(total characters) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func foreignDictionary(words []string) stringTested with go test. Try it yourself first, then compare. It is explained step by step on the Advanced Graphs · Dijkstra & Spanning Trees lesson page.
// AlienOrder: letter order implied by a sorted list of words, or "" if it is contradictory. func AlienOrder(words []string) string { next := map[byte]map[byte]bool{} indeg := map[byte]int{} for _, w := range words { for i := 0; i < len(w); i++ { if _, ok := indeg[w[i]]; !ok { indeg[w[i]] = 0 next[w[i]] = map[byte]bool{} } } } for i := 0; i+1 < len(words); i++ { a, b := words[i], words[i+1] if len(a) > len(b) && a[:len(b)] == b { return "" // "abc" can never come before "ab" } for j := 0; j < len(a) && j < len(b); j++ { if a[j] != b[j] { // the first difference is the only rule this pair gives us if !next[a[j]][b[j]] { next[a[j]][b[j]] = true indeg[b[j]]++ } break } } } var queue []byte for c := 'a'; c <= 'z'; c++ { // fixed scan order keeps the output deterministic if d, ok := indeg[byte(c)]; ok && d == 0 { queue = append(queue, byte(c)) } } var out []byte for len(queue) > 0 { c := queue[0] queue = queue[1:] out = append(out, c) var outs []byte for to := range next[c] { outs = append(outs, to) } sort.Slice(outs, func(i, j int) bool { return outs[i] < outs[j] }) for _, to := range outs { if indeg[to]--; indeg[to] == 0 { queue = append(queue, to) } } } if len(out) != len(indeg) { return "" // a cycle: some letters never reached in-degree 0 } return string(out) } - 6.Cheapest Flights Within K StopsMedium
You have at most k+1 flights. What if you relax all edges exactly one round at a time?
Bellman-Ford limited to k+1 rounds, each round reading from a copy of the previous round's distances. (Dijkstra with state (node, stops) also works.)
Target: O(k · E) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Advanced Graphs · Dijkstra & Spanning Trees lesson page.
// FindCheapestPrice: cheapest src→dst price with at most k stops. // Bellman-Ford limited to k+1 rounds. Each round reads the PREVIOUS round's prices, so one round = one more flight. func FindCheapestPrice(n int, flights [][]int, src, dst, k int) int { prices := make([]int, n) for i := range prices { prices[i] = math.MaxInt } prices[src] = 0 for range k + 1 { next := append([]int(nil), prices...) for _, f := range flights { from, to, cost := f[0], f[1], f[2] if prices[from] != math.MaxInt && prices[from]+cost < next[to] { next[to] = prices[from] + cost } } prices = next } if prices[dst] == math.MaxInt { return -1 } return prices[dst] }