Connecting Roads for Winter - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 45 mins
  • 🛠️ Topics: Minimum Spanning Tree, Prim's Algorithm, Dijkstra'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?
  • How do we calculate the cost between two outposts?
    • The cost is the Manhattan distance: |x_i - x_j| + |y_i - y_j|.
  • Can the outposts be connected in any order?
    • Yes, as long as the total cost to connect all outposts is minimized.
  • What should we return if there are no outposts?
    • Return 0.
HAPPY CASE
Input: outposts = [0, 0], [2, 2], [3, 10], [5, 2], [7, 0](/codepath/compsci_guides/wiki/0,-0],-[2,-2],-[3,-10],-[5,-2],-[7,-0)
Output: 20
Explanation: The minimum total cost to connect the outposts is 20. We calculate the cost using Manhattan distances and find the minimum spanning tree.

EDGE CASE
Input: outposts = []
Output: 0
Explanation: No outposts are present, so the total cost is 0.

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 Connecting Points or Minimum Spanning Tree problems, we want to consider the following approaches:

  • Prim's Algorithm: Efficient for finding the minimum cost to connect all nodes in a graph.
  • Manhattan Distance Calculation: Used to calculate the cost between any two outposts.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use Prim's algorithm to find the minimum cost to connect all outposts. Treat the outposts as nodes in a graph, where the edges between nodes represent the Manhattan distance between outposts. Prim's algorithm will help find the minimum spanning tree that connects all nodes.

1) Initialize a priority queue to store (cost, node) pairs, starting from outpost 0.
2) Use a set to track the visited outposts.
3) Initialize the total cost to 0.
4) While not all outposts are visited:
    a) Pop the minimum cost node from the priority queue.
    b) If the node has been visited, skip it.
    c) Add the node to the visited set and add its cost to the total cost.
    d) For all unvisited neighboring nodes, calculate the Manhattan distance and push the distance and node to the priority queue.
5) Return the total cost once all outposts are connected.

⚠️ Common Mistakes

  • Forgetting to check if a node has already been visited.
  • Not correctly calculating Manhattan distances between nodes.

4: I-mplement

Implement the code to solve the algorithm.

import heapq

# Helper function to calculate Manhattan distance
def manhattan_distance(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

# Function to find the minimum cost to connect all outposts
def prepare_winter_roads(outposts):
    n = len(outposts)
    
    if n == 0:
        return 0
    
    # Initialize variables
    total_cost = 0
    visited = set()
    min_heap = [(0, 0)]  # (cost, index) starting from outpost 0
    
    # Dijkstra-like approach to find the minimum spanning tree
    while len(visited) < n:
        cost, u = heapq.heappop(min_heap)
        
        if u in visited:
            continue
        
        # Add this outpost to the visited set and accumulate the cost
        visited.add(u)
        total_cost += cost
        
        # Check all other outposts and calculate the distance to add to the heap
        for v in range(n):
            if v not in visited:
                dist = manhattan_distance(outposts[u], outposts[v])
                heapq.heappush(min_heap, (dist, v))
    
    return total_cost

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: outposts = [0, 0], [2, 2], [3, 10], [5, 2], 7, 0
  • Expected Output: 20
  • Watchlist:
    • Ensure all outposts are visited once and the total cost is minimized.

6: E-valuate

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

Assume n is the number of outposts.

  • Time Complexity: O(n^2 log n) due to calculating the distance between all pairs and pushing them into the priority queue.
  • Space Complexity: O(n) for storing visited nodes and the priority queue.