Rebuilding the Safe Zones - codepath/compsci_guides GitHub Wiki

Unit 11 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 60 mins
  • 🛠️ Topics: Minimum Spanning Tree, Graph Algorithms, Kruskal’s Algorithm

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Can the graph be disconnected?
    • Yes, in which case it's impossible to connect all camps and we should return -1.
  • How do we ensure that all camps are connected with the minimum cost?
    • By using a minimum spanning tree (MST) algorithm such as Kruskal's.
HAPPY CASE
Input: connections = [1, 2, 5], [1, 3, 6], [2, 3, 1](/codepath/compsci_guides/wiki/1,-2,-5],-[1,-3,-6],-[2,-3,-1), n = 3
Output: 6
Explanation: The minimum cost to connect all camps is 6 (camp 1 to 2 for 5, and camp 2 to 3 for 1).

EDGE CASE
Input: connections = [1, 2, 3], [3, 4, 4](/codepath/compsci_guides/wiki/1,-2,-3],-[3,-4,-4), n = 4
Output: -1
Explanation: Camps 1 and 4 cannot be connected to the other camps.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Minimum Spanning Tree problems, we want to consider the following approaches:

  • Kruskal’s Algorithm: Sort edges by cost, and use Union-Find to ensure no cycles while constructing the minimum spanning tree (MST).
  • Union-Find: Use Union-Find to manage connected components and to efficiently union and find camps as we build the MST.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use Kruskal’s Algorithm to construct the minimum spanning tree. First, sort the edges by cost and use Union-Find to connect the camps while ensuring no cycles. If we manage to connect all camps, return the total cost; otherwise, return -1.

1) Sort all the connections by cost in ascending order.
2) Initialize a Union-Find structure to track connected components.
3) Iterate through the sorted connections, and for each one:
    a) If the two camps are not already connected, union them.
    b) Add the connection cost to the total cost.
    c) Stop early if we have connected all camps with `n - 1` edges.
4) If all camps are connected, return the total cost. Otherwise, return `-1`.

⚠️ Common Mistakes

  • Forgetting to check if all camps are connected by the end of the process.
  • Failing to stop early after forming the MST (when n-1 edges have been used).

4: I-mplement

Implement the code to solve the algorithm.

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size
        self.components = size  # Number of connected components
    
    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])  # Path compression
        return self.parent[p]
    
    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)
        
        if rootP != rootQ:
            # Union by rank
            if self.rank[rootP] > self.rank[rootQ]:
                self.parent[rootQ] = rootP
            elif self.rank[rootP] < self.rank[rootQ]:
                self.parent[rootP] = rootQ
            else:
                self.parent[rootQ] = rootP
                self.rank[rootP] += 1
            self.components -= 1  # Reduce the number of components when we unite two
    
    def connected(self):
        return self.components == 1

def min_rebuilding_cost(n, connections):
    # Sort the connections by the cost in ascending order
    connections.sort(key=lambda x: x[2])
    
    # Initialize Union-Find for n camps (indexed from 1 to n, so size is n+1)
    uf = UnionFind(n + 1)  # We use 1-based indexing for camps
    
    total_cost = 0
    edges_used = 0
    
    # Iterate over each connection in ascending order of cost
    for x, y, cost in connections:
        # Union the two camps if they are not already connected
        if uf.find(x) != uf.find(y):
            uf.union(x, y)
            total_cost += cost
            edges_used += 1
        
        # If we've used n-1 edges, we can stop early (MST complete)
        if edges_used == n - 1:
            break
    
    # Check if all camps are connected
    if edges_used == n - 1:
        return total_cost
    else:
        return -1  # Not all camps are connected

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

  • Input: connections = [1, 2, 5], [1, 3, 6], 2, 3, 1, n = 3
  • Expected Output: 6
  • Watchlist:
    • Ensure that Kruskal’s Algorithm correctly builds the minimum spanning tree.
    • Verify that Union-Find efficiently tracks connected components.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume E is the number of edges and V is the number of nodes (camps).

  • Time Complexity: O(E log E + E log V) due to sorting the edges and using Union-Find operations.
  • Space Complexity: O(V) for storing the parent and rank arrays in Union-Find.