Best Time to Buy and Sell Stock

Problem:

You are given an array prices where prices[i] is the price of a given stock on the $i$-th day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]

Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]

Output: 0

Explanation: In this case, no transactions are done and the max profit = 0.

Solution 1: Naive Brute-Force Solution

def maxProfit(prices):
    mProfit = 0
    for i in range(len(prices)-1):
        profit = max(prices[i+1:]) - prices[i]
        if profit < 0:
            profit = 0
        mProfit = max(mProfit, profit)
    return mProfit

Let us say that you are currently on the $i$-th day and are making a purchase on that day. So the price that you paid for the stock is prices[i]. In order to maximize the profit, you will want to sell your stock on the future date when the stock price is the highest. The highest future price of the stock can be obtained by max(prices[i+1:]). Hence the maximum profit for the purchase made on the $i$-th day is max(prices[i+1:]) - prices[i].

The maximum possible profit is the maximum of max(prices[i+1:]) - prices[i] over all the days from i=0 to i=len(prices)-1.

Runtime: Since the computation of max(prices[i+1:]) takes $n, n-1, \ldots, 1$ steps for each of $i = 0, 1, \ldots, n-1$, the total cost is $n(n+1)/2$. Hence the runtime is $O(n^2)$. Therefore, the above algorith will run into “Time Exceeded” error for very large $n$ on LeetCode.

Since we are only using two constant local variables, the space complexity is $O(1)$.

Solution 2: Two-Pointer Solution

def maxProfit(prices):
    mProfit = 0
    purchasePtr = salePtr = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[purchasePtr]:
            salePtr = i
        else:
            purchasePtr = i
        if salePtr > purchasePtr:
            mProfit = max(mProfit, prices[salePtr] - prices[purchasePtr])
    return mProfit

In the two-pointer solution above, we maintain two pointers, namely, purchasePtr and salePtr, both of which are initialized to 0. When the current price, prices[i] is larger than the price currently indexed by the purchasePtr, i.e: prices[purchasePtr], we would preferrably want to sell the set. So, we update the salePtr to the current index. Otherwise, the current price is smaller or equal, so we update the purchasePtr to i.

If the price difference between the prices pointed to by the salePtr and the purchasePtr (i.e: prices[salePtr] - prices[purchasePtr]), then we compare it with the current maximum profit, mProfit and update it.

Once we reach the end of the prices list, mProfit will contain the maximum possible profit.

Runtime Since we are iterating through the for loop only once, the runtime is $O(n)$. The space complexity is obviously $O(1)$.

Back to Two Pointers Problems

Anusha Murali

Best Time to Buy and Sell Stock

anusha-murali.github.io