Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews.

Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe, and many more top tech companies.

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 to sell that stock in the future.

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

Test case#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.

Test case#2

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints

1 <= prices.length <= 10⁵ (The prices array will have 1 to 100,000 elements in the array).

Understanding the problem?

We know how stock markets are, and the question says, Buy Low, Sell High. So, we are given an input array containing integers, which are the price of stocks on a given day i.

At any given time, we can only purchase one stock before selling it, and only then can we consider purchasing another stock. Our goal is to maximize profits from each transaction.

"Test-Case 1 clearly explains purchasing low-priced stocks and selling them for maximum profits."

Illustration

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

When trading stocks, selling a stock on day one and buying it on day two is impossible. This goes against the basic principles of stock trading.

To maximize our profit, we can purchase the stock on the second day and sell it on the fifth day, then use the funds to purchase the stock with the highest value on the fifth day. The diagram below provides a visual representation of the maximum profit that can be obtained from the given array of stock prices.

As shown in the below figure, we are going to buy the stock on the day 2 and sell on the day 5, which gives us the maximum profit of 6 - 1, i.e., 5.

Thought process

My first thoughts when looking at this problem and the questions I have are:

1. This is prices array, so I believe there are no negative prices?
2. What are the constraints? What if there's only a single element in the prices array?
3. What if the stock price on day 1 is high and on all other days is lower? Should I return 0?

Once the above questions are discussed with the interviewer, I will propose different ways to solve this problem. The ones that come to my mind right now are:

1. Brute force / Naive approach
2. Using extra auxiliary Space
3. One pass or Greedy approach

Approach 1: Naive/Brute force

Intuition

So, how will we keep track of the smallest and the largest numbers while traversing the array?

With this idea in mind, we can have two loops running, and the algorithmic steps are as follows.

Algorithm

1. Initialize a variable maxProfit to 0. This variable will be used to keep track of the maximum profit.
2. The outer loop represents the day on which you consider buying the stock. Iterate through each day as a potential buying day (buyDay) from 0 to prices.length - 1.
3. The inner loop represents the day on which you consider selling the stock. For each buying day (buyDay), iterate through the subsequent days as potential selling days (sellDay) from the next day to the last day.
4. In the inner loop:
   1. Calculate the current profit by subtracting the price on the buying day (prices[buyDay]) from the price on the selling day (prices[sellDay]), which can be currentProfit = prices[sellDay] - prices[buyDay]
   2. Now, update the maxProfit , by doing maxProfit = Math.max(maxProfit, currentProfit)
5. Continue the iterations, considering different buying and selling days.
6. After completing both loops, return the final value of maxProfit.

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int buyDay = 0; buyDay < prices.length; buyDay += 1) {
            for (int sellDay = buyDay + 1; sellDay < prices.length; sellDay += 1) {
                int currentProfit = prices[sellDay] - prices[buyDay];
                maxProfit = Math.max(maxProfit, currentProfit);
            }
        }
        return maxProfit;
    }
}

Complexity Analysis

Time complexity: is O(n^2).

Space complexity: Space is O(1), Only variables are used here maxProfit, i, and j. All these three variables store 4 integer bytes and their values are updated on each iteration. So the total space occupied are 3 * 4 = 12 bytes, which is constant.

Using auxiliary space

Intuition

This approach is not recommended because we use extra space to store an auxiliary array. Can we do better than this? 🤔

Yes, a better approach uses linear search through the array. This is for your practice.

Algorithm

1. Create an auxiliary array aux of the same length as the prices array. Store the maximum right-side stock price at each of these indexes.
2. Initialize the last element of the aux array (aux[prices.length - 1]) with the last price in the prices array (prices[prices.length - 1]). Because this is the max price and there are no right elements.
3. Iterate backward through the prices array, starting from the prices.length - 2 to 0.
   • For each index i, set aux[i] to the maximum value between the current price (prices[i]) and the next day's maximum price (aux[i + 1]).
4. Initialize a variable profit to 0. This variable will be used to keep track of the maximum profit.
5. Iterate through each day in the prices array.
   • For each day (i):
     • Calculate the current profit by subtracting the current price (prices[i]) from the pre-calculated maximum price (aux[i]), using currProfit = aux[i] - prices[i]
• Update profit with the maximum of its current value and the calculated currProfit using profit = Math.max(currProfit, profit)
6. After completing the iteration, return the final value of profit.

class Solution {
    public int maxProfit(int[] prices) {
        int[] aux = new int[prices.length];
        aux[prices.length - 1] = prices[prices.length - 1];
        for (int i = aux.length - 2; i >= 0; i--) {
            aux[i] = Math.max(prices[i], aux[i + 1]);
        }

        int profit = 0;

        for (int i = 0; i < prices.length; i++) {
            int currProfit = aux[i] - prices[i];
            profit = Math.max(currProfit, profit);
        }
        return profit;
    }
}

Complexity Analysis

Time complexity: Time is O(N), where N is the number of elements in the prices array.

Space complexity: Space is O(N), we used an auxiliary array to store the max stock on the right side of each price array element.

One pass [Greedy approach]

Intuition

We used auxiliary or extra space for the max elements to the element's right. But that takes an order N space, which is not at all recommended, plus a bad approach.

Here we keep track of the lowest left price and find the difference between largest price & lowest price.

We are greedy and buy the lowest stocks in a day and sell them for higher profits in the future.

Algorithm

1. Initialize minprice to Integer.MAX_VALUE and maxprofit to 0. These variables will be used to keep track of the minimum price and maximum profit.
2. Iterate through each day in the prices array.
   • For each day (i):
     • If the current price (prices[i]) is less than minprice, update minprice to the current price.
     • Else, if the difference between the current price and minprice is greater than maxprofit, update maxprofit with this difference.
3. After completing the iteration, return the final value of maxprofit.

class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

// Refactoring above code for readability
class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int minPrice = Integer.MAX_VALUE;

        for (int price : prices) {
            if (price < minPrice)
                minPrice = price;
            else
                maxProfit = Math.max(maxProfit, price - minPrice);
        }

        return maxProfit;
    }
}

Complexity Analysis

Time complexity: Time is O(N), where N is the number of elements in the prices array.

Space complexity: Space is O(1).