Q2 - Max Profit With K Transactions

Imagine you have a sequence of potential prices for licensing various shows and movies, represented as an array of positive integers, where each integer corresponds to the price of a single title available on a given day. Additionally, you're given a fixed number k, which limits the number of licensing transactions you can conduct. A transaction involves acquiring the rights to a title on one day and releasing it later for viewership, generating profit.

You must come up with a strategy to maximize your returns from these transactions within the limit set by k. It's not mandatory to exhaust all k transactions; your aim is to achieve the highest profit with the transactions you choose to make.

Key Constraints to keep in mind (if not provided, remember to ask questions):

• You can hold only one title's rights at a time, which means you cannot acquire a new title before releasing the one you currently hold.
• Each acquisition and subsequent release count as one transaction.
• Your strategy should ensure that after all transactions, the cumulative profit is maximized under the constraint that you can make at most k acquisitions and releases.

Input: prices = [3, 7, 1], k = 2
Output: 4
Explanation: Acquire on day 1 (price = 3) and release on day 2 (price = 7), profit = 7-3 = 4.

Input: prices = [7, 2, 8, 4, 1, 3], k = 3
Output: 8
Explanation: Acquire on day 2 (price = 2) and release on day 3 (price = 8), profit = 8-2 = 6.
Then, acquire on day 5 (price = 1) and release on day 6 (price = 3), profit = 3-1 = 2.
Total profit is 6+2 = 8.

Input: prices = [8, 7, 3, 2, 1], k = 2
Output: 0
Explanation: You cannot create a positive profit here. Total profit = 0.

Solution 1 (Recommended)

Let's walk through the dynamic programming solution for the prices = [6, 13, 2, 40, 80, 100] and k = 3 to visualize each step. This will help us build our solution for this problem.

• We create a table dp of dimensions (k + 1) x (length of prices), which is (4 x 6) in our case. Rows represent up to k transactions and columns represent days. The first row (k=0) will only be 0 because the profit will be 0 if there is no transaction. The first column will also be 0 because the profit will be 0 on day 1 (you cannot sell anything on day 1).

For k = 1 (1 transaction):

• Day 1 (j = 0): No transaction possible.
• Day 2 (j = 1): Buy at 6, sell at 13: dp[1][1] = 7.
• Day 3 (j = 2): No improvement over day 1: dp[1][2] = 7.
• Day 4 (j = 3): Buy at 2, sell at 40: dp[1][3] = 38.
• Day 5 (j = 4): Buy at 2, sell at 80: dp[1][4] = 78.
• Day 6 (j = 5): Buy at 2, sell at 100: dp[1][5] = 98.

For k = 2 (2 transactions):

• Day 1 (j = 0): No transaction possible.
• Day 2 (j = 1): Buy at 6, sell at 13: dp[2][1] = 7.
• Day 3 (j = 2): No change from k = 1: dp[2][2] = 7.
• Day 4 (j = 3): Buy at 6, sell at 13, then buy at 2, sell at 40: dp[2][3] = 45.
• Day 5 (j = 4): Buy at 6, sell at 13, then buy at 2, sell at 80: dp[2][4] = 85.
• Day 6 (j = 5): Buy at 6, sell at 13, then buy at 2, sell at 100: dp[2][5] = 105.

For k = 3 (3 transactions):

• Day 1 (j = 0): No transaction possible.
• Day 2 (j = 1): Buy at 6, sell at 13: dp[3][1] = 7.
• Day 3 (j = 2): No change from k = 1: dp[3][2] = 7.
• Day 4 (j = 3): Buy at 6, sell at 13, then buy at 2, sell at 40: dp[3][3] = 45.
• Day 5 (j = 4): Buy at 6, sell at 13, then buy at 2, sell at 80: dp[3][4] = 85.
• Day 6 (j = 5): Buy at 6, sell at 13, then buy at 2, sell at 100: dp[3][5] = 105.

• Each dp[k][j-1] cell represents the maximum profit achievable with up to k transactions by day j (mind the indexing).
• dp[1][j-1] shows the profit for up to 1 transaction, dp[2][j-1] for up to 2 transactions by day j, and so on.
• The profit increases significantly with the second transaction, but a third transaction does not add additional profit.
• The final answer will always be the lower right corner of the matrix (e.g., dp[k][len(prices)-1] = dp[-1][-1]).
• The Max Profit is dp[3][5] = 105, representing the maximum profit achievable with up to 3 transactions by day 6.

Now that we understand the intuition behind our solution, let's jump into the implementation:

1) Dynamic Programming Array Initialization

# If there are fewer than 2 prices, no profit can be made.
if len(prices) < 2: return 0

# 1)Dynamic Programming Array Initialization
dp = [[0] * len(prices) for i in range(k + 1)]

• Create a 2D DP array dp of size (k + 1) x n where k + 1 is the number of transaction sets (including 0 transactions) and n is the number of days.
• Initialize all elements of dp[0][j] and dp[i][0] to 0, since the profit is 0 with 0 transactions or 0 on the 1st day.
• dp[i][j-1] represents the maximum profit with at most i transactions up to day j.

2) Filling the DP Array

# 2)Filling the DP Array
for t in range(1, k + 1):
    max_transaction = -prices[0]
    for d in range(1, len(prices)):
        # 3)Calculating max profit for each day. Either we sell at day (d) or not.
        dp[t][d] = max(dp[t][d - 1], prices[d] + max_transaction)
        max_transaction = max(max_transaction, -prices[d] + dp[t - 1][d])

• For each transaction set t from 1 to k, and for each day d from 1 to n - 1:
  • We calculate the maximum profit for dp[t][d] using two components:
    • The maximum profit if we don't do any transaction on day d (e.g., previous max profit): dp[t][d-1].
    • The maximum profit if we sell on the d'th day. This means that there must be a day x where we previously bought, but did not sell since we are only now selling on day d. We should also not forget that we already accumulated profit up until this particular day x.
      • This would translate to prices[d] + max(-prices[x] + dp[t-1][x]) where 0 ≤ x < d.
      • The positive value of prices[d] is because we are selling the stock at that price, increasing our profit.
      • We are looking for a previous day x on which we bought a stock and did not sell yet. When sold, it will decrease the profit, hence -prices[x].
      • We had already accumulated profit up until the chosen day = x, and its value is dp[t-1][x].
      • We are looking for day = x to maximize the value of the above equation.

3) Calculating Profit for Each Day

for d in range(1, len(prices)):
    # 3)Calculating max profit for each day. Either we sell at day (d) or not.
    dp[t][d] = max(dp[t][d - 1], prices[d] + max_transaction)
    max_transaction = max(max_transaction, -prices[d] + dp[t - 1][d])

• For each possible number of transactions 1 ≤ t ≤ k for each day 1 ≤ d < n, the max profit dp[t][d]:
  • dp[t][d-1], or
  • prices[d] + max(-prices[x] + dp[t-1][x]) where 0 ≤ x < d.

4) Result

• The final result, dp[k][n-1], will give us the maximum profit achievable with at most k transactions by the last day.

Complexity Analysis

• Time Complexity: O(nk), where n is the number of days (length of the prices array) and k is the number of transactions.
  • We iterate through all days for each of the k transactions, resulting in n * k iterations.
• Space Complexity: O(nk), due to the 2D DP array of size (k + 1) * n.
  • This array stores the maximum profit for each day for each possible number of transactions, resulting in a space requirement proportional to n * k.

Below is the code implementing the solution outlined above. Both time and space complexities are O(nk). We recommend thoroughly understanding this solution and starting with it in your interview before introducing the optimal solution. Your interviewers will likely ask about potential improvements to this solution, providing an ideal opportunity to present the second solution that will be discussed in the next section.

# O(nk) time | O(nk) space
def max_profit(k, prices):
    # If there are fewer than 2 prices, no profit can be made.
    if len(prices) < 2: return 0
    
    # 1)Dynamic Programming Array Initialization
    dp = [[0] * len(prices) for i in range(k + 1)]
    
    # 2)Filling the DP Array
    for t in range(1, k + 1):
        max_transaction = -prices[0]
        for d in range(1, len(prices)):
            # 3)Calculating max profit for each day. Either we sell at day (d) or not.
            dp[t][d] = max(dp[t][d - 1], prices[d] + max_transaction)
            max_transaction = max(max_transaction, -prices[d] + dp[t - 1][d])

    return dp[-1][-1]

Solution 2 (Optimal)

Below, we present the optimal solution to our problem. The time complexity remains unchanged at O(nk), but the space complexity improves to O(n). Despite being the optimal solution, it is less intuitive. We recommend initially using Solution 1 in your interview. Netflix interviewers are likely to ask follow-up questions, and swiftly transitioning to a more optimal solution demonstrates your quick thinking and eagerness for growth. In the next section, we will go over the intuition behind this solution.

# O(nk) time | O(n) space
def max_profit(k, prices):
    # If there are fewer than 2 prices, no profit can be made.
    if len(prices) < 2: return 0
    
    # 1) Initialization of Arrays.
    even_profits = [0] * len(prices)
    odd_profits = [0] * len(prices)

    for t in range(1, k + 1):
        # 2) Alternating between arrays.
        max_transaction = -prices[0]
        if t % 2 == 0:
            curr_profits = even_profits
            prev_profits = odd_profits
        else:
            curr_profits = odd_profits
            prev_profits = even_profits

        for d in range(1, len(prices)):
            # 3)Calculating max profit for each day. Either we sell at day (d) or not.
            curr_profits[d] = max(curr_profits[d - 1], prices[d] + max_transaction)
            max_transaction = max(max_transaction, -prices[d] + prev_profits[d])

    return odd_profits[-1] if k % 2 == 1 else even_profits[-1]

The intuition and the formula for calculating the maximum profit on each day with a specified maximum number of transactions are nearly identical to Solution 1. The primary distinction lies in using two separate 1D arrays instead of a single 2D array, which serves to save space.

1) Initialization

# If there are fewer than 2 prices, no profit can be made.
if len(prices) < 2: return 0

# 1) Initialization of Arrays.
even_profits = [0] * len(prices)
odd_profits = [0] * len(prices)

• If there are fewer than 2 prices, no profit can be made, so the function returns 0.
• Two arrays, even_profits and odd_profits, are initialized with zeros. They will store the maximum profits at each day for the current and previous transactions, respectively. This is where the space optimization occurs. Instead of keeping a 2D array of size k × n, we are using just two 1D arrays of size n.
• Imagine the question had max k = 3 transactions. Then, in the first iteration, the even_profits array would hold the max profits when k = 0, and odd_profits array would hold when k = 1. In the next iteration, the even_profits array would hold the max profits when k = 2, and the odd_profits array would hold when k = 3, so on and so forth. They would build up on top of each other, eliminating the need for a 2D array.

2) Alternating Between Arrays

for t in range(1, k + 1):
    # 2) Alternating between arrays.
    max_transaction = -prices[0]
    if t % 2 == 0:
        curr_profits = even_profits
        prev_profits = odd_profits
    else:
        curr_profits = odd_profits
        prev_profits = even_profits

    for d in range(1, len(prices)):
        # 3)Calculating max profit for each day. Either we sell at day (d) or not.
        curr_profits[d] = max(curr_profits[d - 1], prices[d] + max_transaction)
        max_transaction = max(max_transaction, -prices[d] + prev_profits[d])

• Depending on whether t is odd or even, the function swaps the roles of curr_profits and prev_profits. This alternation allows the function to keep track of the current and previous transaction's profits without needing a 2D array.
• For instance, the even_profits array formed for k = 2 will act as the prev_profits to help populate the curr_profits array, which would be the odd_profits array for k = 3.

3) Calculating Profit for Each Day

for d in range(1, len(prices)):
    # 3)Calculating max profit for each day. Either we sell at day (d) or not.
    curr_profits[d] = max(curr_profits[d - 1], prices[d] + max_transaction)
    max_transaction = max(max_transaction, -prices[d] + prev_profits[d])

• The logic is the same as Solution 1. It's either:
  • The maximum profit if we don't do any transaction on day d (e.g., previous max profit):
    • curr_profits[d - 1]
  • The maximum profit if we sell on the d-th day:
    • prices[d] + max(-prices[x] + prev_profits[x]) where 0 ≤ x < d.

4) Updating maxTransaction

max_transaction = max(max_transaction, -prices[d] + prev_profits[d])

• As introduced before, the max_transaction variable represents the maximum profit that can be obtained from previous transactions up to the current day, considering the cost of buying a stock on the current day.
• At each day d, max_transaction is recalculated to consider whether it's more profitable to have bought the stock on this current day d rather than on any earlier day.
• It is calculated as max(max_transaction, -prices[d] + prev_profits[d]).
• prices[d]: Cost of buying the stock on the current day.
• prev_profits[d]: The maximum profit that could have been achieved on all previous days (up to day d) with one less transaction (since prev_profits array holds the profits for t-1 transactions).
• The idea is to keep track of the most profitable point (day) to purchase the stock considering the profits from previous transactions.
• max_transaction effectively tracks the best "entry point" (buying day) so far, taking into account the profits that could have been accumulated from previous transactions up until that day.

5) Result

• Finally, the function returns the last element of odd_profits or even_profits, depending on whether k is odd or even. This element represents the maximum profit achievable with k transactions.

Complexity Analysis

• Time Complexity: O(nk), where n is the number of days (length of prices array) and k is the number of transactions. The time complexity remains unchanged as we need to go through each combination of (t, d) where 0 ≤ t ≤ k and 0 ≤ d < n.
• Space Complexity: O(n): By using only two arrays (even_profits and odd_profits) instead of a 2D array, the space complexity is reduced to O(n), where n is the number of days.

The intuition and the formula for calculating the maximum profit on each day with a specified maximum number of transactions are nearly identical to Solution 1. The primary distinction lies in using two separate 1D arrays instead of a single 2D array, which serves to save space.

Final Notes

If you are preparing for an SDE interview with Netflix, anticipate encountering this problem. It's a difficult problem, but you've got this! Remember to start with Solution 1, even though Solution 2 is more optimal. Demonstrating your ability to quickly adapt to a more optimal solution based on your interviewer's feedback, rather than directly starting with Solution 2, will showcase your analytical thinking and collaborative skills. Clearly and elaborately explain your intuition and thought process to your interviewers. If asked whether you can further optimize your solution, avoid revealing the answer immediately, as it might suggest prior knowledge. Instead, engage with your interviewers collaboratively. Ask questions and create an impression that the solution was reached through teamwork. Remember, they are seeking not someone who knows everything, but a team player adept at working with others to devise the best solutions!

Below, we will reiterate the essential points mentioned above in bullet form. While we acknowledge that this is a recapitulation, we emphasize these details because we believe there is a high likelihood that you will encounter this question or a similar dynamic programming problem in your interview:

1. Begin with the Basics: Understand the foundational concept of dynamic programming and its application to maximize stock trading profits. A strong grasp of the basics will serve as a stepping stone to more advanced strategies.

2. Master the Table Method: Familiarize yourself with creating and filling out a dynamic programming table. This visual aid is crucial for understanding and explaining your approach to solving the problem.

3. Deep Dive into the Problem: Break down the problem into smaller, manageable parts. Start by handling cases with fewer transactions and progressively add complexity by increasing the number of transactions.

4. Clarify the Transaction Limits: Be clear about the constraints of the problem, especially the maximum number of transactions allowed (k). This will help you tailor your solution to the specific limits set by the question.

5. Optimize with Thoughtful Trade-offs: Discuss the trade-offs between time complexity and space complexity. In the interview, you may need to explain why you would choose a solution with better space efficiency over one with better time efficiency, or vice versa.

6. Communicate Your Solution Clearly: As you walk through your solution, pay special attention to articulating the logic behind each step. Netflix values candidates who can explain complex ideas in a simple and coherent manner.

7. Engage with the Interviewer: If the interviewer suggests modifications or probes for further optimization, engage in the discussion. This will demonstrate your ability to adapt and work collaboratively.

8. Discuss Complexity Nuances: Be prepared to dive into a detailed discussion about the time and space complexity of your solution. Netflix interviewers appreciate candidates who can analyze and articulate the efficiency of their code.

9. Showcase Your Problem-Solving Journey: Remember, Netflix is interested in your problem-solving process as much as the final answer. Narrate the journey you take to arrive at the solution, showing your logical progression and adaptability.

10. Demonstrate Collaborative Spirit: Display a willingness to work through the problem as if it's a team effort, suggesting a mindset that aligns well with Netflix's collaborative culture.

11. Avoid Premature Optimization: While it's important to strive for the most efficient solution, don't jump straight to advanced optimizations. Build up to them and show your interviewer that you can iterate and improve your approach.

You got this champ!