List All Escape Routes - codepath/compsci_guides GitHub Wiki

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

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 60 mins
  • 🛠️ Topics: Grid Traversal, Depth-First Search, Breadth-First Search, 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?
  • What is considered a valid escape route?
    • Any path consisting only of safe zones (1s) leading to the bottom-right corner of the grid.
  • Can infected zones (0s) be part of the path?
    • No, infected zones (0s) are impassable.
  • Can multiple routes exist from the same starting point?
    • Yes, but we only need to verify if at least one path exists.
HAPPY CASE
Input: grid = [
    [1, 0, 1, 0, 1],
    [1, 1, 1, 1, 0],
    [0, 0, 1, 0, 0],
    [1, 0, 1, 1, 1]
]
Output: [(0, 0), (0, 2), (1, 0), (1, 1), (1, 2), (1, 3), (2, 2), (3, 2), (3, 3), (3, 4)]
Explanation: These positions can all reach the bottom-right corner of the grid through safe zones.

EDGE CASE
Input: grid = [
    [1, 0],
    [0, 1]
]
Output: [(0, 0)]
Explanation: Only the top-left corner can reach the bottom-right corner.

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

  • Graph Representation: Each cell in the grid is a node, and edges exist between adjacent safe zones.
  • Depth-First Search (DFS): DFS can be used to explore each cell and determine if a path to the target exists.
  • Breadth-First Search (BFS): This could also work, though DFS is commonly used for recursive solutions.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Check each cell in the grid. If the cell is a safe zone (1), perform DFS starting from that cell to determine if there is a path to the safe haven (bottom-right corner).

1) Define a helper function `next_moves` that returns all valid adjacent safe zones that haven't been visited.
2) Define a DFS function `can_reach_safe_haven` that explores the grid starting from a given position and determines if it can reach the safe haven.
3) Loop over each cell in the grid:
    a) If the cell is a safe zone (`1`), call `can_reach_safe_haven` on that cell.
    b) If the DFS returns True, add the cell to the list of escape routes.
4) Return the list of all starting positions that can reach the safe haven.

⚠️ Common Mistakes

  • Forgetting to mark zones as visited during the DFS can lead to infinite loops.
  • Overlooking edge cases where the grid has no safe zones or where the safe haven is unreachable.

4: I-mplement

Implement the code to solve the algorithm.

# Helper function to find valid next moves
def next_moves(position, grid, visited):
    row, col = position
    rows = len(grid)
    cols = len(grid[0])
    
    # Define directions for moving up, down, left, and right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # List to hold the valid next moves
    valid_moves = []
    
    # Check each direction
    for d_row, d_col in directions:
        new_row, new_col = row + d_row, col + d_col
        # Ensure new position is within the grid bounds, is safe (grid[new_row][new_col] == 1),
        # and has not been visited
        if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == 1 and (new_row, new_col) not in visited:
            valid_moves.append((new_row, new_col))
    
    return valid_moves

# DFS function to check if a position can reach the safe haven
def can_reach_safe_haven(position, grid):
    rows, cols = len(grid), len(grid[0])
    target = (rows - 1, cols - 1)
    
    # Use DFS to explore the grid
    def dfs(row, col, visited):
        if (row, col) == target:
            return True
        
        visited.add((row, col))
        
        for next_move in next_moves((row, col), grid, visited):
            if dfs(next_move[0], next_move[1], visited):
                return True
        
        return False
    
    # Start DFS from the current position
    visited = set()
    return dfs(position[0], position[1], visited)

# Main function to list all escape routes
def list_all_escape_routes(grid):
    rows, cols = len(grid), len(grid[0])
    escape_routes = []
    
    # Check each cell in the grid
    for row in range(rows):
        for col in range(cols):
            # If the starting cell is a safe zone (1), check if it can reach the safe haven
            if grid[row][col] == 1 and can_reach_safe_haven((row, col), grid):
                escape_routes.append((row, col))
    
    return escape_routes

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: grid = [ [1, 0, 1, 0, 1], [1, 1, 1, 1, 0], [0, 0, 1, 0, 0], [1, 0, 1, 1, 1] ]
  • Expected Output: [(0, 0), (0, 2), (1, 0), (1, 1), (1, 2), (1, 3), (2, 2), (3, 2), (3, 3), (3, 4)]
  • Watchlist:
    • Ensure visited is being updated correctly during DFS.
    • Check if all valid next moves are being explored properly.
    • Verify that each cell is checked only once.

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) for checking each cell, and O(m * n) for each DFS call. Overall complexity is O((m * n)^2) in the worst case.
  • Space Complexity: O(m * n) due to the recursive DFS call stack and the visited set.