After solving 1000 medium leet code problems found these patterns — Minimum spanning tree

LORY
4 min readMay 1, 2023

Following the leet code patterns series. DFS, BFS, DP, Backtracking, Mono-stack, Presum, Sliding window, Divide and conquer Binary Search, Dijkstra

Here is another one. Even though it could be a surprise to be asked to solve the minimum spanning tree problem during an interview (only 5 Leetcode problems, 3 are hard,3 locked). Let me quickly walk you through the idea of how it works just in case you may be asked during a FANG interview.

The problem.

1584. Min Cost to Connect All Points

Very classic minimum spanning tree algorithm: but how to identify it as a minimum spanning tree problem? very simple: when you are asked to connect x nodes with minimum y. 2 things you need to do:

  • connect all nodes
  • within minimum cost (or distance or time or weight)

e.g. connect all the stations with minimum cost; connect all the network switches with minimum distance; connect x nodes with minimum y.

Ok, you got it.

Now Let’s start to solve the problem.

Prim’s algorithm

The approach is greedy thinking+heap.

Prim’s idea: #1 Imagine you are asked to build a bridge between the town, and you pick one of the towns to start, #2 Every time you only put the minimum effort to build the bridge. #3 How to get the “minimal cost node”? So let’s start from node1, node1 connect to self cost is 0, then see what are the connectable towns from node1, save all the <cost, reachable_node> pair into a min-heap, #4 the heap here is to make sure every time you populate will get a minimal cost node.

Back to the Leetcode question: Given the graph and all edges cost like below, connect the below nodes using minimum cost.

How Prim’s algorithm works step by step is as below

  • Start from node a
  • use a Heap to track the: <cost, connectable node>
  • Check duplicate every time when populating <cost, node> from the min heap
  • push the new reachable <nodes, cost>

--

--

LORY

A channel which focusing on developer growth and self improvement