Gary's Pokédollar Trading Strategy II - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25 mins
  • 🛠️ Topics: Dynamic Programming

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 maximum profit Gary can make from trading Pokéballs, following the cooldown rule after selling.
  • Can Gary make multiple trades in a single day?
    • No, Gary can only hold one trade at a time and must sell before buying again.
  • What happens if there is only one day of trading?
    • No trades can be made in this case.
HAPPY CASE
Input: 
    prices = [1, 2, 3, 0, 2]
Output: 
    3
Explanation:
    Gary should buy on day 1, sell on day 2, rest on day 3, and buy on day 4 and sell on day 5.

EDGE CASE
Input: 
    prices = [1]
Output: 
    0
Explanation:
    With only one day, no trades can be made.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Arrays or Dynamic Programming, and strategies or patterns in those categories.

For Trading Problems with Cooldown, we want to consider the following approaches:

  • Dynamic Programming (DP): Use state transitions to track the maximum profit Gary can make for each day, considering whether he buys, sells, or rests.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use dynamic programming to simulate the state transitions. We maintain three DP arrays: buy, sell, and cooldown to keep track of the maximum profit for each day based on whether Gary is buying, selling, or resting.

Steps:

  1. Initialization:

    • If the prices array is empty or has only one day, return 0.
    • Initialize three DP arrays:
      • buy[i] tracks the maximum profit if Gary buys on day i.
      • sell[i] tracks the maximum profit if Gary sells on day i.
      • cooldown[i] tracks the maximum profit if Gary is resting on day i.

  2. Base Case:

    • On day 0, Gary can only buy, so:
      • buy[0] = -prices[0]
      • sell[0] = 0
      • cooldown[0] = 0

  3. State Transitions:

    • For each day i from 1 to n - 1, compute:
      • buy[i]: The maximum profit if Gary buys on day i, either by buying today or keeping the previous buy.
      • sell[i]: The maximum profit if Gary sells on day i, either by selling today or keeping the previous sell.
      • cooldown[i]: The maximum profit if Gary rests today, either by continuing the previous cooldown or resting after selling.

  4. Return the Result:

    • On the last day, Gary's maximum profit will either be in the sell or cooldown state.

4: I-mplement

Implement the code to solve the algorithm.

def max_pokedollar_profit(prices):
    if not prices:
        return 0
    
    n = len(prices)
    if n == 1:
        return 0
    
    # Initialize the DP arrays
    buy = [-float('inf')] * n
    sell = [0] * n
    cooldown = [0] * n
    
    # Base case: First day transactions
    buy[0] = -prices[0]  # Buying on the first day

    for i in range(1, n):
        # Transitions for each day
        buy[i] = max(buy[i - 1], cooldown[i - 1] - prices[i])  # Buy on day i or keep previous buy
        sell[i] = max(sell[i - 1], buy[i - 1] + prices[i])  # Sell on day i or keep previous sell
        cooldown[i] = max(cooldown[i - 1], sell[i - 1])  # Cooldown after selling
    
    # The maximum profit will be in the sell or cooldown state on the last day
    return max(sell[-1], cooldown[-1])

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: prices = [1, 2, 3, 0, 2]
  • Expected Output: 3

Example 2:

  • Input: prices = [1]
  • Expected Output: 0

6: E-valuate

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

Assume n is the number of days.

  • Time Complexity: O(n) because we compute the state transitions for each day.
  • Space Complexity: O(n) for storing the buy, sell, and cooldown arrays.