An Easier Way to Solve All “Stock Trading” Questions on Leetcode

The “Best Time to Buy and Sell Stock” family of problems is popular on Leetcode and is asked by top companies, including Citadel, Apple, Bloomberg, and Amazon.

You can read this post for free on https://santal.tech/an-easier-way-to-solve-all-stock-trading-questions-on-leetcode/.

In this post, we will discuss how to solve the hardest problem in this family, Best Time to Buy and Sell Stock IV, and you can decompose the solution to solve the easier versions of the question.

Here’s the description:

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

The example provided is:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

This guide will show you how to solve these problems using a simple idea of a DFS search.

Think of the problem as a state machine. Each state has the following features:

• can_buy (boolean): Are we currently holding a stock? In other words, can we purchase a stock in our current state?
• curr_idx (integer): What is our current "day" (represented as our position in the prices array)?
• num_txns (integer): How many transactions have we made?

What does our initial state look like?

• can_buy: True. We aren’t holding a stock, so we can purchase a stock.
• curr_idx: 0. We’re starting at day 0— so the start of the prices.
• num_txns: 0. We haven’t made any transactions.

What are the valid transitions we can take from one state to another?

• We can always do nothing and move to the next day; we’ll just increment curr_idx and keep the other two values unchanged.
• When can_buy is True, we could buy the stock. This will cost prices[curr_idx].
• When can_buy is False, that means we’re holding a stock. We could sell this stock and gain prices[curr_idx].

When are we in a terminal state (i.e. we can’t transition to another valid state)?

• When there are no more prices, i.e. curr_idx == len(prices).
• When we’ve made the maximum number of allowed transactions, i.e. num_txns == k.

If you think of all the valid states and their transitions, we can model this as a graph.

Let’s use the example provided:

• prices=[2,4,1]
• k = 2

(Please click to expand the image!)

Let’s take a look at the leftmost circle, which represents our initial state. From there, we have two options:

1. We can do nothing and move to the next price. can_buy and num_txns are unchanged, but curr_idx increments by 1.
2. We can buy a stock. can_buy becomes False, since we can only hold one stock at a time. num_txns doesn’t change until we sell a stock!

Also note the value associated with buying a stock; we know this has a transition cost of -2. Similarly, if we were to sell a stock, we’d have a transition gain of the current selling price.

The rightmost circles in green represent our terminal states. We can no longer take action from those states because our curr_idx is 3 and we’ve reached the end of the prices array.

We see that the second bottom-most circle with value=2 is our winner. If we buy a stock at price 2 then sell at price 4, we have an overall profit of 2.

Note, another way of reaching a terminal state is if num_txns==k; we can no longer buy or sell a stock, so we can end our traversal there.

You might be asking, “What about which stock we’re holding?” or “How much profit have we made so far”? Do we need to capture those in our current state as well?

Because we’re subtracting price of a stock when we purchase it and adding the price of a stock when we sell it, we see that just keeping track of the state change is sufficient.

But wait, isn’t this inefficient?

We’re technically exploring every state here, and we’re also doing of repeated work! See the two red circles; they are the exact same state, so we shouldn’t be traversing each of the subtrees from that position twice.

Let’s cache the result! Our keys are (curr_idx, can_buy, num_txns). When we encounter a state already in the cache, we can just return that the best value we got from that state.

Our final space and time complexities are both O(len(prices) * 2 * num_txns)).

Final code

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        cache = {}
        def dfs(curr_idx, can_buy, num_txns):
            if num_txns >= k or curr_idx == len(prices):
                return 0
            key = (curr_idx, can_buy, num_txns)
            if key in cache:
                return cache[key]
            # do nothing
            nothing = dfs(curr_idx + 1, can_buy, num_txns)
            # buy
            if can_buy:
                action = dfs(curr_idx + 1, False, num_txns) - prices[curr_idx]
            # sell
            else:
                action = dfs(curr_idx + 1, True, num_txns + 1) + prices[curr_idx]

            best = max(nothing, action)
            cache[key] = best
            return best
        return dfs(0, True, 0)

What about the other problems?

Best Time to Buy and Sell Stock III

• Find the maximum profit you can achieve. You may complete at most two transactions. You are given an array prices where prices[i] is the price of a given stock on the ith day. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
• All you have to do is hardcode k to 2.

Best Time to Buy and Sell Stock II

• You are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve.
• Remove k entirely.

Best Time to Buy and Sell Stock with Cooldown

• You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions: after you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day). Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
• Modify the state transition when you sell a stock; instead of curr_idx + 1, we’ll use curr_idx + 2.

Best Time to Buy and Sell Stock with Transaction Fee

• You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee. Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
• Modify the state transition when you sell a stock; you’ll also want to subtract the fee, i.e. action = dfs(curr_idx + 1, True) + prices[curr_idx] - fee.

For more articles like this, follow me on Medium. Not a member yet? Join the community. Want more software engineering interview guides and coding question tips? Check out all of my writing organized by topic in this article.

If you have any requests for what I should write, please let me know!