Best Time to Buy and Sell Stock

In this post, I will explain how to approach the popular coding interview question: "Best Time to Buy and Sell Stock". This problem tests fundamental dynamic programming/array concepts, so having a deep understanding of this problem will serve as a stepping stone for harder ones.

Problem statement:

You are given an array prices where prices[i] is the price of a given stock on the ith 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.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input:prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

I recommend that you pause and try to come up with a solution yourself.

Solution

We will begin by presenting a brute-force solution and further optimizing it to arrive to the optimal solution.

Brute Force Solution

Recall that

profit = prices[i] - prices[j] where i > j;

In this case, we simply calculate the profit corresponding to all possible pairs of transactions and find out the maximum profit. This can be achieved using two loops as follows:

public class Solution {
    public int maxProfit(int prices[]) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit)
                    maxprofit = profit;
            }
        }
        return maxprofit;
    }
}

The time complexity of the above approach is O(n^2). The code inside the two loops will run n(n - 1)/2 times (where n is the length of the prices array).

The space complexity is O(1), given that only two variables are being used. In other words, the memory requirements for this algorithm does not depend on the size of the input prices array.

One Pass Solution

This problem can be solved by looping through the array once. The idea is to iterate through the array from right to left. As we do so, we store the maximum price encountered so far and use it to calculate the profit at each current element.

class Solution {
    public int maxProfit(int[] prices) {
        int maxPriceRight = prices[prices.length - 1], maxProfit = 0;

        for(int i = prices.length - 2; i>= 0; i--){
            maxProfit = Math.max(maxPriceRight - prices[i], maxProfit);
            maxPriceRight = Math.max(maxPriceRight, prices[i]);
        }

        return maxProfit;
    }
}

The reason why we maximize the maxPriceRight as we iterate through the array is because we are only allowed to perform one transaction. Therefore, if we encounter a higher price, it is guaranteed that it will yield a higher overall profit.

This problem was taken from leetcode.com