Celebrity Rivalry Loops - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-35 mins
• 🛠️ Topics: Graph Traversal, DFS, Cycle Detection

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?

• Q: What does the rivalries list represent?
  • A: Each index i in rivalries represents a celebrity, and the list contains other celebrities they have a rivalry with.
• Q: What is the goal of the problem?
  • A: The goal is to determine whether any group of celebrities is involved in a rivalry loop (cycle), where the rivalry eventually leads back to the original celebrity.
• Q: How should the function return the result?
  • A: The function should return True if a rivalry loop exists and False otherwise.

HAPPY CASE
Input: 
```python
rivalries_1 = [
    [1],
    [0, 2],
    [1, 3],
    [2]
]
```
Output:
```markdown
False
Explanation: There are no rivalry loops in this setup. All rivalries are linear, and no celebrity's rivalry leads back to them through others.
```

EDGE CASE
Input: 
```python
rivalries_2 = [
    [1],
    [2],
    [3],
    [0]
]
```
Output:
```markdown
True
Explanation: There is a rivalry loop between the celebrities: 0 -> 1 -> 2 -> 3 -> 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 Cycle Detection in an Undirected Graph, we want to consider the following approaches:

• Depth First Search (DFS): DFS is useful for detecting cycles in an undirected graph. If we encounter a visited node that is not the parent node, we have detected a cycle.
• Graph Traversal: The rivalry problem is naturally represented as a graph, where we want to find cycles (rivalry loops) in an undirected graph.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use DFS to explore all rivalries. While traversing, if we encounter a node that has already been visited and is not the parent of the current node, a cycle (rivalry loop) has been detected. If DFS completes without finding a cycle, return False.

1) Initialize a `visited` list to keep track of which celebrities have already been visited.
2) Define a recursive DFS function:
   a) Mark the current celebrity as visited.
   b) Explore all rival celebrities (neighbors).
   c) If a rival has not been visited, recursively perform DFS on that rival.
   d) If a rival has been visited and is not the parent of the current celebrity, a cycle (rivalry loop) has been found.
3) For each unvisited celebrity, run DFS to detect rivalry loops.
4) If a cycle is detected during DFS, return `True`. If no cycles are found, return `False`.

⚠️ Common Mistakes

• Forgetting to handle disconnected components in the graph, which can lead to incomplete DFS traversals.
• Not handling self-loops correctly, although the problem assumes no self-loops exist.

4: I-mplement

Implement the code to solve the algorithm.

def has_rivalry_loop(rivalries):
    n = len(rivalries)
    visited = [False] * n

    def dfs(current, parent):
        visited[current] = True
        
        # Explore all rivalries (neighbors)
        for rival in rivalries[current]:
            if not visited[rival]:
                # Recur for the unvisited rival
                if dfs(rival, current):
                    return True
            elif rival != parent:
                # If we visit a rival that is not the parent, we found a cycle
                return True
        
        return False

    # Try DFS from every node (some nodes might be disconnected)
    for celebrity in range(n):
        if not visited[celebrity]:
            if dfs(celebrity, -1):  # Start DFS with no parent (-1)
                return True
    
    return False

5: R-eview

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

• Input:

rivalries_1 = [
    [1],
    [0, 2],
    [1, 3],
    [2]
]
rivalries_2 = [
    [1],
    [2],
    [3],
    [0]
]

print(has_rivalry_loop(rivalries_1))  # Expected output: False
print(has_rivalry_loop(rivalries_2))  # Expected output: True

• Output:

False
True

6: E-valuate

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

• Time Complexity: O(V + E), where V is the number of celebrities (vertices) and E is the number of rivalries (edges). Each celebrity and rivalry is visited once in the DFS traversal.
• Space Complexity: O(V + E) for storing the graph and the visited array.