Ash’s Team Battle Strategy - codepath/compsci_guides GitHub Wiki

Unit 12 Session 1 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30 mins
  • 🛠️ Topics: Dynamic Programming, Subsequence

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 is the goal of the problem?
    • The goal is to find the longest alternating subsequence of Pokémon such that no two consecutive Pokémon have the same type.
  • What is considered alternating?
    • A sequence is considered alternating if consecutive elements differ in their type, i.e., they alternate between physical and special attackers.
HAPPY CASE
Input: 
    pokemon = [""Pikachu"", ""Bulbasaur"", ""Charmander""]
    types = [0, 0, 1]
Output: 
    ['Pikachu', 'Charmander']
Explanation:
    Ash can choose a subsequence like [""Pikachu"", ""Charmander""] because their types differ.

EDGE CASE
Input: 
    pokemon = [""Squirtle"", ""Pidgey"", ""Rattata"", ""Gengar""]
    types = [1, 0, 1, 1]
Output: 
    ['Squirtle', 'Pidgey', 'Rattata']
Explanation:
    Ash can select [""Squirtle"", ""Pidgey"", ""Rattata""] since their types alternate as required.

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 alternating subsequence problems, we want to consider the following approaches:

  • Dynamic Programming (DP): DP is useful for tracking the longest alternating subsequence as we move through the array.
  • Greedy Approach: You could greedily pick the Pokémon that alternates in type, but DP ensures the longest possible subsequence.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use dynamic programming to find the longest alternating subsequence. At each step, we'll decide whether to include the current Pokémon based on the type of the previous one, ensuring we only extend the subsequence if their types differ.

Steps:

  1. Initialization:

    • Create a dp list where each entry is a tuple containing the subsequence and its length. Initialize it with the first Pokémon.

  2. Fill DP Table:

    • Loop through the list of Pokémon starting from the second element.
    • If the type of the current Pokémon differs from the previous one, extend the subsequence. Otherwise, start a new subsequence.

  3. Return the Result:

    • Return the subsequence with the maximum length from the dp list.

4: I-mplement

Implement the code to solve the algorithm.

def team_battle_strategy(pokemon, types):
    n = len(pokemon)
    if n == 0:
        return []
    
    # Start with the first Pokémon as part of the first subsequence
    dp = [([pokemon[0]], 1)]  # List of (subsequence, length)
    
    for i in range(1, n):
        # If the types alternate, extend the current subsequence
        if types[i] != types[i - 1]:
            dp.append((dp[-1][0] + [pokemon[i]], dp[-1][1] + 1))  # Extend the sequence
        else:
            dp.append(([pokemon[i]], 1))  # Start a new sequence
    
    # Return the longest subsequence by comparing their lengths
    return max(dp, key=lambda x: x[1])[0]  # Return the longest sequence

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: pokemon = [""Pikachu"", ""Bulbasaur"", ""Charmander""], types = [0, 0, 1]
  • Expected Output: ['Pikachu', 'Charmander']

Example 2:

  • Input: pokemon = [""Squirtle"", ""Pidgey"", ""Rattata"", ""Gengar""], types = [1, 0, 1, 1]
  • Expected Output: ['Squirtle', 'Pidgey', 'Rattata']

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the length of the input array.

  • Time Complexity: O(n) because we iterate through the list of Pokémon once.
  • Space Complexity: O(n) to store the dp list of subsequences.