Cyclical Roads in Kingdom - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 45 mins
• 🛠️ Topics: Depth-First Search (DFS), Graph Traversal

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?

• What defines a cyclical road?
  • A cyclical road is a path that starts and ends at the same square, and all squares along the path have the same character (representing the road type).
• Can we return to the previous square directly?
  • No, you cannot return to the square you just visited.

HAPPY CASE
Input: kingdom = [
    [""a"", ""a"", ""a"", ""a""],
    [""a"", ""b"", ""b"", ""a""],
    [""a"", ""b"", ""b"", ""a""],
    [""a"", ""a"", ""a"", ""a""]
]
Output: True
Explanation: There is a cycle involving the 'a' roads along the outer edge of the kingdom.

EDGE CASE
Input: kingdom = [
    [""c"", ""c"", ""c"", ""a""],
    [""c"", ""d"", ""c"", ""c""],
    [""c"", ""c"", ""e"", ""c""],
    [""f"", ""c"", ""c"", ""c""]
]
Output: True
Explanation: There is a cycle involving the 'c' roads in the center of the kingdom.

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

• Depth-First Search (DFS): DFS can be used to explore all roads starting from each square. We need to check if we can form a cycle by returning to the starting point after visiting other squares.
• Cycle Detection: This problem involves detecting a cycle in a grid, where each square with the same character is a part of the cycle.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Perform DFS starting from each unvisited square in the grid. While performing DFS, track the previous square to avoid returning directly to the last visited square. If we encounter the starting square and the path length is 4 or more, we have found a cycle.

1) Define a helper function `next_moves` to get valid neighboring cells with the same road type (character).
2) Define a DFS function that explores all neighboring squares and checks for a cycle.
3) Use DFS to explore each square in the grid. For each square, if a cycle is found, return `True`.
4) If no cycles are found, return `False`.

⚠️ Common Mistakes

• Forgetting to track the previous square can result in false positives for cycles.
• Not ensuring that the path length is at least 4 before checking for a cycle.

4: I-mplement

Implement the code to solve the algorithm.

# Helper function to find valid next moves (same character, not the previous square)
def next_moves(kingdom, row, col, prev_row, prev_col):
    moves = [
        (row + 1, col),  # down
        (row - 1, col),  # up
        (row, col + 1),  # right
        (row, col - 1)   # left
    ]
    
    possible = []
    for r, c in moves:
        if 0 <= r < len(kingdom) and 0 <= c < len(kingdom[0]):
            if (r, c) != (prev_row, prev_col) and kingdom[r][c] == kingdom[row][col]:
                possible.append((r, c))
    
    return possible

# DFS function to check for cyclical roads
def dfs(kingdom, row, col, start_row, start_col, prev_row, prev_col, visited, path_length):
    visited.add((row, col))
    
    for r, c in next_moves(kingdom, row, col, prev_row, prev_col):
        if (r, c) not in visited:
            # Continue the DFS
            if dfs(kingdom, r, c, start_row, start_col, row, col, visited, path_length + 1):
                return True
        elif (r, c) == (start_row, start_col) and path_length >= 4:
            # If we encounter the starting cell and the path length is >= 4, we have found a cycle
            return True
    
    return False

# Main function to detect cyclical roads
def detect_cyclical_roads(kingdom):
    visited = set()
    
    for row in range(len(kingdom)):
        for col in range(len(kingdom[0])):
            if (row, col) not in visited:
                if dfs(kingdom, row, col, row, col, -1, -1, visited, 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.

Example 1:

• Input: kingdom = [ [""a"", ""a"", ""a"", ""a""], [""a"", ""b"", ""b"", ""a""], [""a"", ""b"", ""b"", ""a""], [""a"", ""a"", ""a"", ""a""] ]
• Expected Output: True
• Watchlist:
  • Ensure that DFS correctly detects the cycle involving the 'a' roads on the outer edge.
  • Verify that the visited set tracks all explored squares to avoid redundant checks.

6: E-valuate

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

Assume m is the number of rows and n is the number of columns in the grid.

• Time Complexity: O(m * n) because each cell is visited once during DFS.
• Space Complexity: O(m * n) due to the visited set and DFS stack.