Defending the Safehouse - 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: Grid Traversal, Breadth-First Search (BFS), Pathfinding

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?
  • Can we flip the entrance or the safehouse cells?
    • No, the entrance and the safehouse cannot be flipped.
  • What happens if there is already no path between the entrance and the safehouse?
    • If no path exists initially, the city is already disconnected, and the answer is True.
  • How do we define ""disconnected""?
    • Disconnected means that no path exists between the entrance (0, 0) and the safehouse (m - 1, n - 1).
HAPPY CASE
Input: city = [
    [1, 1, 1],
    [0, 0, 1],
    [1, 1, 1]
]
Output: False
Explanation: No single flip can disconnect the path from (0,0) to (m-1,n-1).

EDGE CASE
Input: city = [
    [1, 0, 0],
    [1, 1, 0],
    [0, 1, 1]
]
Output: True
Explanation: Flipping the cell at (1, 1) disconnects the path between the entrance and the safehouse.

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:

  • Breadth-First Search (BFS): BFS can be used to check if a path exists from the entrance to the safehouse, exploring all possible moves level by level.
  • Pathfinding: We are checking if a valid path exists between two points in the grid and whether flipping a single cell disconnects this path.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Perform BFS to check if a path exists from the entrance (0, 0) to the safehouse (m - 1, n - 1). Then, try flipping each accessible cell (except the entrance and the safehouse) to see if it disconnects the city.

1) Define a helper function `has_path` that uses BFS to check if there is a path from the entrance to the safehouse.
2) If no path exists initially, return `True` (the city is already disconnected).
3) Try flipping each cell (except the entrance and the safehouse) and check if the path is now disconnected.
4) If flipping a cell successfully disconnects the city, return `True`.
5) If no cell flip disconnects the city, return `False`.

⚠️ Common Mistakes

  • Forgetting to reset a flipped cell back to its original state after checking.
  • Not handling the case where the city is already disconnected.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

# Helper function to check if a path exists from (0,0) to (m-1,n-1)
def has_path(city):
    m, n = len(city), len(city[0])
    
    # If the entrance or the safehouse is blocked, there's no path
    if city[0][0] == 0 or city[m-1][n-1] == 0:
        return False
    
    # BFS to check if there's a path from (0, 0) to (m-1, n-1)
    queue = deque([(0, 0)])
    visited = [[False] * n for _ in range(m)]
    visited[0][0] = True
    
    while queue:
        row, col = queue.popleft()
        
        # If we reached the bottom-right corner, return True
        if row == m - 1 and col == n - 1:
            return True
        
        # Explore the right and downward directions
        for new_row, new_col in [(row + 1, col), (row, col + 1)]:
            if 0 <= new_row < m and 0 <= new_col < n and not visited[new_row][new_col] and city[new_row][new_col] == 1:
                visited[new_row][new_col] = True
                queue.append((new_row, new_col))
    
    return False

# Main function to determine if we can disconnect the safehouse
def can_disconnect_safehouse(city):
    m, n = len(city), len(city[0])
    
    # If there's no initial path, the city is already disconnected
    if not has_path(city):
        return True
    
    # Try flipping each cell (except the entrance and the safehouse)
    for row in range(m):
        for col in range(n):
            if (row == 0 and col == 0) or (row == m - 1 and col == n - 1):
                continue  # Skip entrance and safehouse
            
            # Flip the cell
            city[row][col] = 1 - city[row][col]
            
            # Check if the path is now disconnected
            if not has_path(city):
                return True  # Successfully disconnected
            
            # Restore the cell back to its original state
            city[row][col] = 1 - city[row][col]
    
    # If no flip disconnects the city, return False
    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: city = [ [1, 1, 1], [0, 0, 1], [1, 1, 1] ]
  • Expected Output: False
  • Watchlist:
    • Ensure that the initial path check is correct.
    • Verify that all possible cell flips are tried and that the city is properly disconnected when applicable.

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 * (m + n)) because for each cell, we perform a BFS which can traverse the entire grid.
  • Space Complexity: O(m * n) due to the BFS queue and visited array.