Minimum Spanning Tree (Kruskal)

📋

Minimum Spanning Tree (Kruskal)

Edge cases:

</>

IDE

def kruskalMST(n: int, edges: list) -> int:public int kruskalMST(int n, int[][] edges)int kruskalMST(int n, vector<vector<int>>& edges)function kruskalMST(n, edges)

def kruskalMST(n, edges):
    # Write your solution here
    pass

class Solution {
    public int kruskalMST(int n, int[][] edges) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int kruskalMST(int n, vector<vector<int>>& edges) {
    // Write your solution here
    return 0;
}

function kruskalMST(n, edges) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Sum of all edgesFailing to detect cycles, adding all edges regardless of connectivity.✅ Implement union-find to check if adding an edge forms a cycle before union.

Wrong: Incorrect MST weight due to ignoring sortingNot sorting edges by weight before processing.✅ Sort edges ascending by weight before union-find processing.

Wrong: Non-zero MST weight for single node graphNo base case for n=1, returning default or error.✅ Add base case: if n==1 return 0 immediately.

Wrong: Including heavier parallel edgesNot prioritizing smallest edge between same nodes.✅ Sort edges by weight and union-find prevents adding heavier parallel edges forming cycles.

Wrong: TLE on large inputsUsing brute force or inefficient cycle detection.✅ Use Kruskal's algorithm with sorting and efficient union-find (path compression + union by rank).

✓

Test Cases

Focus on handling graphs with minimal or uniform edges correctly.

Watch out for subtle bugs in cycle detection and edge selection.

Optimize your solution to handle large graphs efficiently.

t1_01basic

Input{"n":4,"edges":[[0,1,1],[1,2,2],[0,2,3],[2,3,4]]}

Expected7

⏱ Performance - must finish in 2000ms

Pick edges (0,1), (1,2), and (2,3) with weights 1, 2, and 4 respectively. Total = 7, which is minimal.

💡 Sort edges by weight and try adding them if they don't form a cycle.

💡 Use union-find to efficiently detect cycles when adding edges.

💡 Implement Kruskal's algorithm: union sets only if roots differ.

Why it failed: Incorrect MST weight indicates union-find or sorting bug. Fix by ensuring edges are sorted ascending and union only if roots differ.

✓ Correct MST weight confirms proper sorting and union-find usage.

t1_02basic

Input{"n":5,"edges":[[0,1,2],[0,2,3],[1,2,1],[1,3,4],[3,4,5]]}

Expected12

⏱ Performance - must finish in 2000ms

Edges chosen: (1,2)=1, (0,1)=2, (1,3)=4, (3,4)=5 total 12 minimal MST weight.

💡 Check all edges sorted by weight and add if no cycle.

💡 Union-find helps to detect cycles efficiently.

💡 Choose edges (1,2), (0,1), (1,3), (3,4) for minimal total weight 12.

Why it failed: Failing to pick smallest edges first or incorrect union-find leads to wrong MST weight. Fix sorting and union-find logic.

✓ Correct MST weight shows proper edge selection and cycle detection.

t2_01edge

Input{"n":1,"edges":[]}

Expected0

⏱ Performance - must finish in 2000ms

Single node graph has MST weight 0 as no edges are needed.

💡 Consider the base case where no edges exist.

💡 MST weight for a single node is zero by definition.

💡 Return 0 immediately if n=1 or edges empty.

Why it failed: Returning non-zero or error on single node input. Fix by adding base case: if n==1 return 0.

✓ Correctly handles single node with MST weight 0.

t2_02edge

Input{"n":3,"edges":[[0,1,5],[1,2,5],[0,2,5]]}

Expected10

⏱ Performance - must finish in 2000ms

All edges have same weight 5; MST includes any two edges without cycle, total 10.

💡 When edges have equal weights, any spanning tree with n-1 edges is minimal.

💡 Ensure your algorithm does not depend on unique weights.

💡 Pick any two edges that connect all nodes without cycles.

Why it failed: Algorithm fails with equal weights due to incorrect cycle detection or sorting. Fix by stable sorting and proper union-find.

✓ Correct MST weight with equal edges confirms stable sorting and union-find.

t2_03edge

Input{"n":3,"edges":[[0,1,10],[0,1,1],[1,2,2]]}

Expected3

⏱ Performance - must finish in 2000ms

Multiple edges between nodes 0 and 1; choose smallest weight edge (0,1,1) plus (1,2,2) total 3.

💡 When multiple edges connect same nodes, pick the smallest weight edge.

💡 Sort edges by weight to prioritize smaller edges.

💡 Union-find will prevent adding heavier parallel edges forming cycles.

Why it failed: Including heavier parallel edge causes MST weight to be too large. Fix by sorting edges ascending and union-find cycle check.

✓ Correctly picks smallest parallel edge and forms MST.

t2_04edge

Input{"n":4,"edges":[[0,1,1],[1,2,2],[2,3,3],[0,3,4],[1,3,5]]}

Expected6

⏱ Performance - must finish in 2000ms

Edges form multiple cycles; MST excludes edges that form cycles. MST edges: (0,1)=1, (1,2)=2, (2,3)=3 total 6.

💡 Detect cycles to exclude edges that close cycles.

💡 Union-find helps to avoid adding edges that form cycles.

💡 Always pick edges with smallest weights first.

Why it failed: Including edges that form cycles leads to MST weight > 6. Fix by proper union-find cycle detection and skipping edges that connect already connected components.

✓ Correct MST weight confirms cycle detection and edge selection.

t3_01corner

Input{"n":4,"edges":[[0,1,1],[1,2,2],[2,3,1],[0,3,10],[1,3,5]]}

Expected4

⏱ Performance - must finish in 2000ms

Greedy trap: picking edges by local minimum may choose (0,3,10) or (1,3,5) prematurely. Correct MST edges: (0,1)=1, (2,3)=1, (1,2)=2 total 4.

💡 Beware of greedy traps that pick heavier edges early.

💡 Kruskal's algorithm requires sorting all edges ascending.

💡 Avoid adding edges that form cycles even if they seem cheaper locally.

Why it failed: Greedy approach picking heavier edges first leads to MST weight 8 or more. Fix by sorting all edges ascending before union-find.

✓ Correct MST weight confirms proper global sorting and cycle detection.

t3_02corner

Input{"n":3,"edges":[[0,1,1],[1,2,2],[0,2,3],[0,2,1]]}

Expected2

⏱ Performance - must finish in 2000ms

Confusion between 0/1 and unbounded: MST must include edges without duplicates. MST edges: (0,1)=1, (0,2)=1 total 2.

💡 MST edges are unique; no repeated edges allowed.

💡 Union-find prevents cycles, ensuring edges are chosen once.

💡 Do not add multiple edges between same nodes unless they reduce MST weight.

Why it failed: Allowing duplicate edges or ignoring union-find causes incorrect MST weight 3 or 4. Fix by enforcing union-find cycle checks and unique edges.

✓ Correct MST weight shows proper 0/1 edge inclusion.

t3_03corner

Input{"n":5,"edges":[[0,1,1],[1,2,1],[2,3,1],[3,4,1],[0,4,10],[1,3,10]]}

Expected4

⏱ Performance - must finish in 2000ms

Edges forming multiple cycles: MST excludes heavy edges (0,4) and (1,3). MST edges: (0,1), (1,2), (2,3), (3,4) total 4.

💡 Detect cycles to exclude heavy edges that form cycles.

💡 Union-find helps to avoid adding edges that close cycles.

💡 Always pick edges with smallest weights first.

Why it failed: Including heavy edges that form cycles leads to MST weight 14. Fix by proper union-find cycle detection and skipping edges that connect already connected components.

✓ Correct MST weight confirms cycle detection and edge selection.

t4_01performance

Input{"n":100,"edges":[[0,1,1],[1,2,1],[2,3,1],[3,4,1],[4,5,1],[5,6,1],[6,7,1],[7,8,1],[8,9,1],[9,10,1],[10,11,1],[11,12,1],[12,13,1],[13,14,1],[14,15,1],[15,16,1],[16,17,1],[17,18,1],[18,19,1],[19,20,1],[20,21,1],[21,22,1],[22,23,1],[23,24,1],[24,25,1],[25,26,1],[26,27,1],[27,28,1],[28,29,1],[29,30,1],[30,31,1],[31,32,1],[32,33,1],[33,34,1],[34,35,1],[35,36,1],[36,37,1],[37,38,1],[38,39,1],[39,40,1],[40,41,1],[41,42,1],[42,43,1],[43,44,1],[44,45,1],[45,46,1],[46,47,1],[47,48,1],[48,49,1],[49,50,1],[50,51,1],[51,52,1],[52,53,1],[53,54,1],[54,55,1],[55,56,1],[56,57,1],[57,58,1],[58,59,1],[59,60,1],[60,61,1],[61,62,1],[62,63,1],[63,64,1],[64,65,1],[65,66,1],[66,67,1],[67,68,1],[68,69,1],[69,70,1],[70,71,1],[71,72,1],[72,73,1],[73,74,1],[74,75,1],[75,76,1],[76,77,1],[77,78,1],[78,79,1],[79,80,1],[80,81,1],[81,82,1],[82,83,1],[83,84,1],[84,85,1],[85,86,1],[86,87,1],[87,88,1],[88,89,1],[89,90,1],[90,91,1],[91,92,1],[92,93,1],[93,94,1],[94,95,1],[95,96,1],[96,97,1],[97,98,1],[98,99,1],[0,99,1000],[1,98,1000],[2,97,1000],[3,96,1000],[4,95,1000],[5,94,1000],[6,93,1000],[7,92,1000],[8,91,1000],[9,90,1000]]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 nodes, edges ~110; O(m log m) sorting and O(m α(n)) union-find must complete within 2s.

💡 Sorting edges is O(m log m), union-find operations are almost O(1).

💡 Avoid brute force subsets which are exponential.

💡 Use efficient union-find with path compression and union by rank/size.

Why it failed: Brute force or naive cycle detection causes TLE. Fix by implementing Kruskal's algorithm with efficient union-find.

✓ Algorithm runs within time confirming O(m log m) complexity.

Practice

1. You are given a list of equations between variables, each either asserting equality (e.g., a==b) or inequality (e.g., a!=b). Which algorithmic approach best guarantees an efficient and correct solution to determine if all equations can be satisfied simultaneously?

easy

A. Union-Find data structure with two passes: first union all equalities, then check inequalities

B. Greedy approach that processes equations in input order, merging sets as it goes

C. Dynamic programming to track variable equivalences and contradictions

D. Brute force checking all pairs of variables for contradictions repeatedly

Solution

1. Step 1: Understand problem constraints

   The problem requires grouping variables into equivalence classes based on equalities and then verifying inequalities do not contradict these groups.

2. Step 2: Identify suitable algorithm

   Union-Find efficiently merges sets for equalities and then checks inequalities in a separate pass, ensuring correctness and near-linear time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Union-Find handles equivalence classes efficiently [OK]

Hint: Separate equality and inequality processing [OK]

Common Mistakes:

• Assuming greedy order works
• Using DP without clear state
• Brute force is too slow

2. What is the time complexity of the optimal union-find solution for the Most Stones Removed with Same Row or Column problem, given n stones?

medium

A. O(n α(n)) where α is the inverse Ackermann function, due to union-find operations

B. O(n^2) due to checking all pairs of stones

C. O(n log n) because of sorting stones by coordinates

D. O(n) since each stone is processed once without extra overhead

Solution

1. Step 1: Analyze union-find operations

   Each union/find operation runs in nearly O(1) amortized time, specifically O(α(n)) where α is inverse Ackermann.

2. Step 2: Count total operations

   We perform at most 2n find operations and n union operations, total O(n α(n)).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Union-find with path compression and rank -> O(n α(n)) [OK]

Hint: Union-find with path compression -> near-linear time [OK]

Common Mistakes:

• Assuming O(n^2) from brute force pairwise checks
• Confusing sorting complexity with union-find
• Ignoring inverse Ackermann function in complexity

3. Identify the bug in the following union-find code snippet used to solve the Most Stones Removed with Same Row or Column problem:

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}
        self.count = 0

    def find(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 0
            self.count += 1
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            # BUG: missing decrement of count here

uf = UnionFind()
for x, y in stones:
    uf.union(x, ~y)

return len(stones) - uf.count

medium

A. Line where rank is incremented after union

B. Line where parent is assigned in find method

C. Line where new nodes are initialized in find

D. Line missing decrement of count after union

Solution

1. Step 1: Understand count variable role

   Count tracks number of connected components, incremented on new node creation.

2. Step 2: Identify missing update

   After union merges two components, count must decrement but code misses this step.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Without decrement, count overestimates components -> wrong answer [OK]

Hint: Count must decrease on union of distinct sets [OK]

Common Mistakes:

• Forgetting to decrement count after union
• Incorrect rank updates
• Misusing parent assignments in find

4. What is the time complexity of the optimal union-find based solution that sorts edges and processes them to remove the maximum number of edges while keeping the graph traversable for both Alice and Bob?

medium

A. O(n^2) due to checking connectivity repeatedly for each edge

B. O(m log m + m α(n)) where m is number of edges and α is inverse Ackermann function

C. O(m n) because union-find operations can be linear in worst case

D. O(m + n) since union-find operations are almost constant time

Solution

1. Step 1: Identify sorting cost

   Sorting edges costs O(m log m) where m is number of edges.

2. Step 2: Analyze union-find operations

   Union-find operations take O(α(n)) amortized per operation, so total O(m α(n)).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting dominates, union-find nearly constant -> O(m log m + m α(n)) [OK]

Hint: Sorting edges dominates complexity, union-find nearly constant [OK]

Common Mistakes:

• Assuming union-find is O(n) per operation
• Ignoring sorting cost
• Confusing n and m in complexity

5. Suppose the Swim in Rising Water problem is modified so that you can revisit cells multiple times (cycles allowed), and the grid elevations can be negative. Which modification to the union-find approach is necessary to correctly solve this variant?

hard

A. Sort cells by absolute elevation and union in that order to handle negative values.

B. Add a visited set to union-find to prevent cycles during union operations.

C. Use a priority queue (min-heap) to process cells by elevation dynamically instead of sorting all upfront.

D. No change needed; the original union-find with sorting by elevation works as is.

Solution

1. Step 1: Understand impact of negative elevations and revisits

   Negative elevations break sorting assumption; revisiting cells means connectivity can change dynamically.

2. Step 2: Identify suitable data structure

   A priority queue allows processing cells in order of elevation dynamically, handling negative values and revisits correctly.

3. Step 3: Why other options fail

   Sorting by absolute elevation loses ordering semantics; visited sets don't apply to union-find; original approach assumes non-negative elevations and no revisits.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Priority queue enables dynamic elevation processing [OK]

Hint: Dynamic processing needed for negative elevations and revisits [OK]

Common Mistakes:

• Sorting by absolute elevation breaks ordering
• Assuming union-find alone handles cycles
• Ignoring negative elevation impact on sorting