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

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…