Number of Protected Towns - 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 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 defines a ""protected"" town?
    • A protected town is a connected group of 0s (towns) that are completely surrounded by 1s (land) on all sides, including diagonally adjacent cells.
  • Can a town touch the grid's border and still be protected?
    • No, if any part of the town touches the border, it is not protected.
HAPPY CASE
Input: kingdom = [
    [1,1,1,1,1,1,1,0],
    [1,0,0,0,0,1,1,0],
    [1,0,1,0,1,1,1,0],
    [1,0,0,0,0,1,0,1],
    [1,1,1,1,1,1,1,0]
]
Output: 2
Explanation: There are two protected towns in the grid that are completely surrounded by `1`s.

EDGE CASE
Input: kingdom = [
    [0,0,1,0,0],
    [0,1,0,1,0],
    [0,1,1,1,0]
]
Output: 2
Explanation: There are two protected towns in this grid.

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:

  • Depth-First Search (DFS): DFS can be used to explore each unvisited town (connected component of 0s) and check if it is protected.
  • Breadth-First Search (BFS): BFS could also be used, but DFS is often simpler for recursive exploration.
  • Connected Components: Each town can be treated as a connected component, and we need to check if the entire component is protected.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use DFS to explore each unvisited town (a connected group of 0s). For each town, check if it is protected by ensuring that none of its cells touch the border of the grid. If it is protected, increment the count.

1) Define a helper function `next_moves` to get valid neighboring cells.
2) Define a DFS function to explore the entire town and check if it is protected.
3) Use DFS to explore each unvisited town, and for each town, check if it is protected by ensuring that none of its cells touch the border of the grid.
4) If the town is protected, increment the protected town count.
5) Return the number of protected towns.

⚠️ Common Mistakes

  • Forgetting to check grid boundaries when exploring towns during DFS.
  • Not correctly marking towns as visited, leading to repeated exploration.

4: I-mplement

Implement the code to solve the algorithm.

# Helper function to get valid neighboring cells
def next_moves(kingdom, row, 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]):
            possible.append((r, c))
    
    return possible

# DFS function to explore the town and check if it's protected
def dfs(kingdom, row, col, visited):
    stack = [(row, col)]
    visited.add((row, col))
    is_protected = True
    
    while stack:
        r, c = stack.pop()
        
        # If the town touches the border, it's not protected
        if r == 0 or r == len(kingdom) - 1 or c == 0 or c == len(kingdom[0]) - 1:
            is_protected = False
        
        for nr, nc in next_moves(kingdom, r, c):
            if (nr, nc) not in visited and kingdom[nr][nc] == 0:
                visited.add((nr, nc))
                stack.append((nr, nc))
    
    return is_protected

# Main function to count the number of protected towns
def count_protected(kingdom):
    if not kingdom or not kingdom[0]:
        return 0
    
    visited = set()
    protected_count = 0
    
    for row in range(len(kingdom)):
        for col in range(len(kingdom[0])):
            # Start DFS if we find an unvisited '0' (part of a town)
            if kingdom[row][col] == 0 and (row, col) not in visited:
                if dfs(kingdom, row, col, visited):
                    protected_count += 1
    
    return protected_count

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 = [ [1,1,1,1,1,1,1,0], [1,0,0,0,0,1,1,0], [1,0,1,0,1,1,1,0], [1,0,0,0,0,1,0,1], [1,1,1,1,1,1,1,0] ]
  • Expected Output: 2
  • Watchlist:
    • Ensure that DFS correctly explores all cells in each town.
    • Verify that towns touching the grid's border are marked as unprotected.

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.