Decreasing Zombie Path - 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), Memoization

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?
  • How is the path considered ""decreasing""?
    • The number of zombies in each subsequent area traveled must be strictly less than the number in the preceding area.
  • Can we revisit cells during the same path?
    • No, you cannot revisit any cells during the same path.
HAPPY CASE
Input: city = [
    [4, 3],
    [1, 2]
]
Output: 4
Explanation: The longest decreasing path is 4 -> 3 -> 2 -> 1, with a length of 4.

EDGE CASE
Input: city = [
    [1, 2, 18, 3],
    [26, 6, 7, 15],
    [9, 10, 17, 18],
    [14, 15, 16, 22]
]
Output: 9
Explanation: The longest decreasing path is 22 -> 18 -> 17 -> 16 -> 15 -> 10 -> 6 -> 2 -> 1.

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 is used to explore each cell in the grid, looking for decreasing paths.
  • Memoization: Memoization helps avoid redundant calculations by storing the longest path starting from each cell.
  • Dynamic Programming: The problem can also be approached using dynamic programming to build solutions based on previous computations.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Perform DFS starting from each cell in the grid. For each cell, find the longest decreasing path using DFS and store the result in a memoization table to avoid redundant calculations.

1) Define a helper function `next_moves` to get valid neighboring cells (those with fewer zombies).
2) Define a DFS function to explore all valid next moves and calculate the longest decreasing path starting from a given cell.
3) Use memoization to store the longest path for each cell to avoid recalculating.
4) Run DFS from each cell and return the maximum path length.

⚠️ Common Mistakes

  • Forgetting to use memoization can lead to time inefficiencies, as DFS could be called multiple times for the same cell.
  • Not handling edge cases where the grid is empty.

4: I-mplement

Implement the code to solve the algorithm.

# Helper function to find valid next moves (cells with fewer zombies)
def next_moves(position, city):
    row, col = position
    rows, cols = len(city), len(city[0])
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Up, Down, Left, Right
    valid_moves = []
    
    for d_row, d_col in directions:
        new_row, new_col = row + d_row, col + d_col
        if 0 <= new_row < rows and 0 <= new_col < cols and city[new_row][new_col] < city[row][col]:
            valid_moves.append((new_row, new_col))
    
    return valid_moves

# DFS function with memoization to find the longest decreasing path
def dfs(row, col, city, memo):
    if memo[row][col] != -1:  # Return memoized result if already computed
        return memo[row][col]
    
    max_length = 1  # The cell itself is part of the path
    
    # Get all valid next moves (neighboring cells with fewer zombies)
    for new_row, new_col in next_moves((row, col), city):
        max_length = max(max_length, 1 + dfs(new_row, new_col, city, memo))
    
    memo[row][col] = max_length  # Memoize the result
    return max_length

# Main function to find the longest decreasing path
def longest_decreasing_path(city):
    if not city or not city[0]:
        return 0
    
    m, n = len(city), len(city[0])
    memo = [[-1] * n for _ in range(m)]  # Memoization table
    longest_path = 0
    
    # Run DFS from each cell
    for row in range(m):
        for col in range(n):
            longest_path = max(longest_path, dfs(row, col, city, memo))
    
    return longest_path

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 = [ [4, 3], [1, 2] ]
  • Expected Output: 4
  • Watchlist:
    • Ensure that DFS correctly finds the longest path starting from each cell.
    • Verify that memoization is working correctly and avoids redundant calculations.

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, and memoization prevents redundant calculations.
  • Space Complexity: O(m * n) due to the memoization table and DFS stack.