Best Time to Buy and Sell Stock (leetcode)

Today I want to share about some leetcode problems. The solutions that I will share will use a dynamic programming. Here is list of the problems:

• Best Time To Buy & Sell Stocks
• Best Time To Buy & Sell Stocks II
• Best Time To Buy & Sell Stocks III
• Best Time To Buy & Sell Stocks IV
• Best Time To Buy & Sell Stocks with Cooldown
• Best Time To Buy & Sell Stocks with Transaction Fee

Best Time To Buy & Sell Stocks

This is the first problem. We are given a list of stock prices for each day and we want to maximize the profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

For example, we are given a list of stocks = [7,1,5,3,6,4]. From that list we can calculate that the maximum profit is 5, because we will buy at index 1, and sell it at index 4. The price at index 1 is 1, and the price at index 4 is 6. So we have profit 6 -1 = 5.

This is the solution, first we must define a state variable to check if the current day we have bought stock or not. I will use state = 0 if I haven’t bought yet, state = 1 if I already bought, state = 2 if I already sold the stock.

• If state is 0 (haven’t bought), there are 2 possibilities we can do. First, we can wait the next day to buy the stock or we can buy it now.
• If state is 1 (already bought), there are 2 possibilities we can do. First we can wait the next day to sell the stock or we can sell it now.
• If state is 2 (already sold), we can’t buy anymore.

This is the full code.

public int maxProfit(int[] prices) {
    memo = new HashMap<>();
    return solve(0, prices, 0);
}

This is the method that will be called to get the answer. This method will initialize memo variable and call solve method with idx (day) = 0 and state = 0 (haven’t bought).

if (idx == prices.length || state == 2) {
    return 0;
}

This is for the base case, if state = 2 or idx = prices.length we must return 0. state == 2 means we already sold the stock. idx = prices.length means the current day is the day after the last day we can buy/sell the stock.

String key = state + "-" + idx;
Integer mem = memo.get(key);
if (mem != null) {
    return mem;
}

This code means before we calculate the maximum profit, we must check if the same sub problem (idx and state) already occurs before. If yes, then we just return the value in the memo.

int wait = solve(idx + 1, prices, state);

This wait variable means the profit that we will get if the current day we are not buying / selling the stock. If we wait, the state will not change and idx will be moved to the next idx (day).

if (state == 0) {
    int buy = solve(idx + 1, prices, state + 1) - prices[idx];
    if (buy > max) max = buy;
}

This buy variable means the profit that we will get if the current day we are buying the stock. If we buy, the state will change to 1 and idx will be moved to the next idx and the profit will be decreased as much as the current stock price (prices[idx]). And we can only buy if the current state is 0.

else if (state == 1) {
    int sell = solve(idx + 1, prices, state + 1) + prices[idx];
    if (sell > max) max = sell;
}

This sell variable means the profit that we will get if the current day we are selling the stock. If we sell, the state will change to 2 and idx will be moved to the next idx and the profit will be increased as much as the current stock price (prices[idx]). And we can only buy if the current state is 1.

memo.put(key, max);
return max;

This code means we return the maximum profit for the current day. And before we return it, we must store the value in the memo variable. So when the same sub problem occurs (idx and state), we don’t have to calculate again.

Best Time To Buy & Sell Stocks II

This problem is similar to the first problem. The only difference from the first problem is we can do transaction multiple times. So after we sell the stock, we must change the state to 0 again.

int sell = solve(idx + 1, prices, state - 1) + prices[idx];

Best Time To Buy & Sell Stocks III

This problem is similar to the second problem. The only difference between the second problem is we can only do 2 transactions. So we need to add 2 more parameters to the solve method. The first parameter is k, to determine the maximum transaction can be made. The second parameter is tx, to calculate the transactions that have been made.

And every time we sell, we need to increment the tx variable.

int sell = solve(idx + 1, prices, state - 1, tx + 1) + prices[idx];

And if the value of tx is equal to k, it means we have done k transactions and can’t do transactions anymore.

if (idx == prices.length || tx == k) {                                   
    return 0;                               
}

Best Time To Buy & Sell Stocks IV

This problem is similar with the third problem. The only difference between the third problem is we can only do k transactions. So we just need to pass parameter k to solve method based on parameter in maxProfit method instead of hard code it to 2.

Best Time To Buy & Sell Stocks with Cooldown

This problem is similar to the second problem, we can do transactions multiple times. The only difference is after we sell the stock, we can’t buy again the next day.

So after we sell the stock, we must increment idx by 2.

int sell = solve(idx + 2, prices, state - 1) + prices[idx];

And because of that, there is probability if idx > prices.length, so we need to change the condition to idx >= prices.length

if (idx >= prices.length) {
    return 0;
}

Best Time To Buy & Sell Stocks with Transaction Fee

This problem is similar to the second problem, we can do transactions multiple times. The only difference is we need to pay a transaction fee for every transaction. So after we sell the stock, not only we need to increased the profit as much as the stock price, but we need to decreased the profit based on the transaction fee.

int sell = solve(idx + 1, prices, state - 1, fee) + prices[idx] - fee;