Maximum Number of Troops Captured - 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, Breadth-First Search (BFS), Connected Components

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 I move diagonally to capture troops?
    • No, movement is restricted to up, down, left, and right.
  • What should I return if there are no troops on the battlefield?
    • Return 0 if no troops exist.
  • Can the battlefield contain obstacles?
    • Yes, obstacles are represented as 0 and cannot be passed through.
HAPPY CASE
Input: battlefield = [
    [0,2,1,0],
    [4,0,0,3],
    [1,0,0,4],
    [0,3,2,0]
]
Output: 7
Explanation: You can start at (1,3), capture 3 troops, move to (2,3), and capture 4 troops, for a total of 7 troops.

EDGE CASE
Input: battlefield = [
    [0,0],
    [0,0]
]
Output: 0
Explanation: There are no troops on the battlefield, so the output is 0.

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 is useful to explore all connected components of troops starting from any given position and summing up the total number of troops in each connected component.
  • Connected Components: This problem can be framed as finding the largest connected component of troops on the battlefield, where each non-obstacle cell is a node.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use BFS to explore each connected component of troops on the battlefield. Starting from each unvisited troop cell, perform BFS to collect all troops in the connected component and update the maximum number of troops captured.

1) Define a helper function `next_moves` to get valid neighboring troop cells (up, down, left, right).
2) Define a BFS function to explore a connected component of troops starting from a given cell.
3) Initialize a `visited` set to keep track of visited cells.
4) Iterate through the battlefield grid:
    a) If a cell contains troops and has not been visited, perform BFS to find the total number of troops in the connected component.
    b) Update the maximum number of troops captured.
5) Return the maximum number of troops captured.

⚠️ Common Mistakes

  • Forgetting to check grid boundaries during BFS can result in out-of-bounds errors.
  • Not correctly updating or maintaining the visited set can lead to revisiting cells.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

# Helper function to get valid neighboring troop cells
def next_moves(battlefield, row, column):
    moves = [
        (row + 1, column),  # down
        (row - 1, column),  # up
        (row, column + 1),  # right
        (row, column - 1)   # left
    ]
    
    possible = []
    for r, c in moves:
        if 0 <= r < len(battlefield) and 0 <= c < len(battlefield[0]) and battlefield[r][c] > 0:
            possible.append((r, c))
    
    return possible

# BFS function to explore a connected component of troops
def bfs(battlefield, row, column, visited):
    queue = deque([(row, column)])
    visited.add((row, column))
    total_troops = battlefield[row][column]
    
    while queue:
        r, c = queue.popleft()
        for nr, nc in next_moves(battlefield, r, c):
            if (nr, nc) not in visited:
                visited.add((nr, nc))
                total_troops += battlefield[nr][nc]
                queue.append((nr, nc))
    
    return total_troops

# Main function to find the maximum number of troops that can be captured
def capture_max_troops(battlefield):
    if not battlefield or not battlefield[0]:
        return 0
    
    max_troops = 0
    visited = set()
    
    for row in range(len(battlefield)):
        for col in range(len(battlefield[0])):
            if battlefield[row][col] > 0 and (row, col) not in visited:
                # Perform BFS/DFS to find total troops in this connected component
                max_troops = max(max_troops, bfs(battlefield, row, col, visited))
    
    return max_troops

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: battlefield = [ [0,2,1,0], [4,0,0,3], [1,0,0,4], [0,3,2,0] ]
  • Expected Output: 7
  • Watchlist:
    • Ensure that all neighboring troop cells are correctly identified in next_moves.
    • Verify that BFS explores all connected troop cells and sums their values correctly.
    • Check that the visited set is maintained to avoid revisiting cells.

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 at most once during BFS.
  • Space Complexity: O(m * n) due to the queue storing positions of cells and the visited set.