Where it runs
1. The problem
You are wiring up a network of sites (offices, power stations, water tanks), and you have a list of possible connections, each with a cost. Every site must be connected so that any site can reach any other, and you want the total cost as low as possible. Any connection beyond what you need is wasted money. A connection that closes a loop is always waste: its two ends could already reach each other.
That shape (all the nodes connected, no wasted loops, the least total weight) is a minimum spanning tree.
In the last lesson you built union-find (DSU): join two groups, and ask "same group?" in nearly constant time. Kruskal's algorithm uses exactly that.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems that ask for the cheapest way to connect everything, or which links a cheapest network must use. Sort the edges by weight and add each one whose ends are not yet joined, which union-find checks.
Every pair of points is an edge weighted by Manhattan distance, about 5 times 10^5 edges for 1000 points, and Kruskal joins them.
Sort the queries by limit too, add every edge below the current limit, and answer each query with one find.
Run Kruskal once without each edge and once with it forced in, and compare each total with the true minimum.