Escape to the Safe Haven - 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: 45 mins
  • 🛠️ Topics: Grid Traversal, Depth-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 if we start in an unsafe zone?
    • Return False immediately if the start or target zone is unsafe.
  • Can I move diagonally?
    • No, only horizontal and vertical adjacent moves are allowed.
  • Can I revisit previously visited zones?
    • No, once a zone is visited, it should not be revisited.
HAPPY CASE
Input: position = (0, 0), grid = [
    [1, 0, 1, 1, 0],
    [1, 1, 1, 1, 0],
    [0, 0, 1, 1, 0],
    [1, 0, 1, 1, 1]
]
Output: True
Explanation: There exists a safe path to the bottom-right corner.

EDGE CASE
Input: position = (0, 1), grid = [
    [1, 0, 1, 1, 0],
    [1, 1, 1, 1, 0],
    [0, 0, 1, 1, 0],
    [1, 0, 1, 1, 1]
]
Output: False
Explanation: The start position is unsafe, so we cannot move.

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 zone in the grid can be treated as a node, and edges exist between adjacent safe zones.
  • Depth-First Search (DFS): DFS can be used to explore the grid and find a path to the bottom-right corner.
  • Breadth-First Search (BFS): This could also work, but DFS is often simpler to implement for this kind of problem.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Start from the initial position and explore the grid using DFS, ensuring you only move to adjacent safe zones. Keep track of visited zones to avoid cycles and unnecessary reprocessing.

1) Define a helper function `next_moves` that returns all valid adjacent safe zones that haven't been visited.
2) Initialize a set `visited` to keep track of previously visited zones.
3) Use DFS to recursively explore the grid from the starting position:
    a) If the current position is the target, return True.
    b) Mark the current position as visited.
    c) Explore all valid adjacent positions by calling the helper function.
    d) If any recursive call returns True, propagate the result upward.
4) If no path to the target exists, return False.

⚠️ Common Mistakes

  • Forgetting to check if the starting or target position is unsafe.
  • Not marking zones as visited, leading to infinite loops.
  • Failing to handle grids with only unsafe zones.

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

# Main function to determine if the safe haven can be reached
def can_move_safely(position, grid):
    rows, cols = len(grid), len(grid[0])
    start_row, start_col = position
    target = (rows - 1, cols - 1)
    
    # If starting or target position is unsafe, return False immediately
    if grid[start_row][start_col] == 0 or grid[rows - 1][cols - 1] == 0:
        return False
    
    # Initialize the visited set
    visited = set()
    
    # DFS function to explore the grid
    def dfs(row, col):
        if (row, col) == target:
            return True
        
        visited.add((row, col))
        
        # Get valid next moves from the current position using the helper function
        for next_move in next_moves((row, col), grid, visited):
            if dfs(next_move[0], next_move[1]):
                return True
        
        return False
    
    # Start DFS from the initial position
    return dfs(start_row, start_col)

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: position = (0, 0), grid = [ [1, 0, 1, 1, 0], [1, 1, 1, 1, 0], [0, 0, 1, 1, 0], [1, 0, 1, 1, 1] ]
  • Expected Output: True
  • Watchlist:
    • Which cells are marked as visited?
    • What are the values of next_move in each DFS iteration?
    • Are the bounds and grid safety checks working as expected?

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, in the worst case, we might need to visit every cell in the grid.
  • Space Complexity: O(m * n) due to the recursive call stack and the visited set.