Spread the Zombie Cure - 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: Dijkstra’s Algorithm, Graph Representation

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 the travel times work between camps?
    • Each directed edge has a travel time, and the cure can only follow the directed paths.
  • What if some camps are unreachable?
    • Return -1 if any camp cannot be reached from the starting camp.
HAPPY CASE
Input: times = [(2, 1, 1), (2, 3, 1), (3, 4, 1)], n = 4, k = 2
Output: 2
Explanation: Starting from camp 2, the cure reaches camp 1 and camp 3 in 1 unit of time each, and reaches camp 4 via camp 3 in a total of 2 units of time.

EDGE CASE
Input: times = [(1, 2, 1)], n = 2, k = 2
Output: -1
Explanation: There is no direct or indirect communication line connecting camp 2 to camp 1, so camp 1 cannot be reached.

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 Shortest Path problems, we want to consider the following approaches:

  • Dijkstra’s Algorithm: Use Dijkstra’s algorithm to find the shortest time to deliver the cure to all camps by exploring the network in increasing order of travel time.
  • Heap (Priority Queue): A min-heap is used to efficiently retrieve the next camp with the smallest travel time.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Build a graph representation of the network of camps, and use Dijkstra’s algorithm to determine the shortest travel time from the starting camp to all other camps. Return the maximum time needed to reach any camp.

1) Build a graph representation of the network where each node (camp) has a list of directed edges (communication lines).
2) Initialize a distance array with infinite values for all camps, except the starting camp, which has a distance of 0.
3) Use a min-heap (priority queue) to process camps in increasing order of travel time.
4) For each camp, explore its neighbors and update their distances if a shorter path is found.
5) Once all camps have been processed, return the maximum distance. If any camp is unreachable, return -1.

⚠️ Common Mistakes

  • Forgetting to check if all camps are reachable.
  • Not handling disconnected components where some camps cannot be reached.

4: I-mplement

Implement the code to solve the algorithm.

import heapq

# Main function to find the minimum time to spread the cure to all camps
def spread_cure(n, times, k):
    # Build the graph as a regular dictionary with empty lists for each node
    graph = {i: [] for i in range(1, n + 1)}
    
    for u, v, w in times:
        graph[u].append((v, w))
    
    # Distance array to keep track of the shortest time to each node
    dist = {i: float('inf') for i in range(1, n + 1)}
    dist[k] = 0  # The time to reach the starting camp is 0
    
    # Min-heap to get the node with the smallest known distance
    heap = [(0, k)]  # (time, node) starting from node k
    
    # Dijkstra's algorithm
    while heap:
        current_time, u = heapq.heappop(heap)
        
        # If we already found a shorter way to u, skip
        if current_time > dist[u]:
            continue
        
        # Explore neighbors
        for v, w in graph.get(u, []):
            time = current_time + w
            # If a shorter time to v is found, update it and push to the heap
            if time < dist[v]:
                dist[v] = time
                heapq.heappush(heap, (time, v))
    
    # The time it takes for the cure to reach all camps is the maximum distance
    max_time = max(dist.values())
    
    # If there's a camp that is unreachable, return -1
    return max_time if max_time != float('inf') else -1

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: times = [(2, 1, 1), (2, 3, 1), (3, 4, 1)], n = 4, k = 2
  • Expected Output: 2
  • Watchlist:
    • Ensure that Dijkstra’s algorithm correctly computes the shortest time for all camps.
    • Verify that unreachable camps are handled by returning -1.

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 (communication lines) and V is the number of camps (nodes).

  • Time Complexity: O(E log V) because each edge is processed once and the heap operations take log V time.
  • Space Complexity: O(E + V) due to the graph representation and distance array.