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

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

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 15 mins
  • 🛠️ Topics: Dynamic Programming, Array Manipulation

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 help Gary maximize his Pokédollar profit by buying on one day and selling on another future day.
  • Can Gary buy and sell on the same day?
    • No, Gary needs to buy on a different day and sell on a future day.
  • What if Gary cannot make any profit?
    • If no profit can be made, return 0.
HAPPY CASE
Input: 
    prices = [7, 1, 5, 3, 6, 4]
Output: 
    5
Explanation:
    Gary should buy on day 2 at 1 Pokédollar and sell on day 5 at 6 Pokédollars. The profit is `6 - 1 = 5`.

EDGE CASE
Input: 
    prices = [7, 6, 4, 3, 1]
Output: 
    0
Explanation:
    Gary cannot make any profitable trades in this case.

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

  • Greedy Strategy: At each step, we want to minimize the buying price and maximize the selling price.
  • Dynamic Programming: We could use dynamic programming to track the maximum profit achievable by holding or selling a stock.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We can solve this problem by iterating through the prices once and keeping track of the minimum price observed so far. For each day, calculate the profit if we were to sell at that price and keep track of the maximum profit.

Steps:

  1. Initialization:

    • Initialize a variable min_price to a large number (infinity).
    • Initialize a variable max_profit to 0.

  2. Iterate Through Prices:

    • For each day i:
      • Update min_price to be the minimum between the current min_price and prices[i].
      • Calculate the profit by selling at prices[i] and update max_profit if this profit is higher.

  3. Return the Result:

    • Return max_profit, which will store the maximum possible profit.

4: I-mplement

Implement the code to solve the algorithm.

def max_pokedollar_profit(prices):
    # Initialize variables
    min_price = float('inf')
    max_profit = 0
    
    # Loop through each price in the list
    for price in prices:
        # Update the minimum price seen so far
        min_price = min(min_price, price)
        
        # Calculate profit if we sell at the current price
        profit = price - min_price
        
        # Update the maximum profit if this is the best we've seen
        max_profit = max(max_profit, profit)
    
    return max_profit

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 = [7, 1, 5, 3, 6, 4]
  • Expected Output: 5

Example 2:

  • Input: prices = [7, 6, 4, 3, 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 prices in the input.

  • Time Complexity: O(n) because we iterate through the prices array once.
  • Space Complexity: O(1) since we only use a constant amount of extra space.