Solving Best Time to Buy and Sell Stock Leetcode Problem

This was a problem that I didn’t fully understand the first time I saw it. It took me a while to come up with a brute force solution. So I am very happy that I understand it enough to share not one but TWO solutions with you.

Problem:

You are given an array prices where prices[i] is the price of a given stock on the i<sup>th</sup> 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: My initial solution

function maxProfit(prices){
   const profits = []; 

   for (let i = 0; i < prices.length - 1; i++){
     let profit = 0; 
     for (let j = i + 1; j < prices.length; j++){
        let currProfit = prices[j] - prices[i]; 
        if (currProfit > 0 && currProfit > profit){
            profit = currProfit
        }
     }
      profits.push(profit); 
   }

    return profits.length > 0 ? Math.max(...profits) : 0; 
};

Reasoning behind the solution

• Create an array to store profits.

• For each element in the array find the max profit, if any, that can be made if you buy during that day, and sell at all the days after it.

• Add the possible profit that can be made for each day to the profits array.

• Return the largest element from the profits array.

Bugs I encountered:

• My initial return statement was:

•     return Math.max(...profits);
  

• Had to refactor the return statement to also account for situations where there are no profits at all i.e profits.length = 0.

• Math.max returns -Infinity if there are no parameters -(there are none if you spread an empty array) OOPS!

Time Complexity:

Time complexity for this solution is O(N²).

Why? Imagine we start with an array of size N. Using this implementation, we loop over each element and, for each element, we check all the elements after it to find the maximum profit

• We do N - 1 checks for the first value

• N - 2 for the second value

• N - 3 for the third

• N - 4 for the fourth and so forth…

• until we get to the last element which has no comparisons

• The total number of steps is:

$$(N−1)+(N−2)+(N−3)+⋯+1+0$$

• which after some math magic is equal to

$$(N^2 - N)/2$$

• As the size of the array gets larger, the constant term (the 1/2 factor), and non-leading term ( the -N) will be insignificant so we drop them. As a result, the time complexity is O(N²).

• If the above was confusing, dont fret: most of the times when you have 2 nested for loops, you can assume that the time complexity is O(N²).

This solution didn’t pass all the leetcode tests, probably because for very large arrays, the algorithm is so slow, it times out.

Space Complexity:

• By creating an array to store the profits, the space complexity is increased. We are storing a profit for every element which means that for an N element array, the space complexity is O(N).

Solution 2: A linear solution

Shoutout to Mark Saltzman for helping me break this solution down, and go over this linear solution. Lets go!

Algorithm steps

• have a variable, maxProfit, to keep track of the max profit. Initialize it to 0.

• have a variable, buyingPrice, to keep track of buying price. Initialize it to the first element in the array

• loop over the array of prices starting at the second element, looking for a ‘selling price’ which will make the most profit

  • If the price is less than the current buyingPrice, then don’t sell, instead buy at that new lower price.

  • If the price is greater than the current buyingPrice, then sell at that price for a profit.

    • if the profit from selling at that price is bigger than our maxProfit, reassign maxProfit to that profit.

• Return maxProfit

function findMaxProfit(prices) { 

   let maxProfit = 0; 
   let buyingPrice = prices[0]; 

   for (let i = 1; i < prices.length; i++){
      if (prices[i] < buyingPrice){
         buyingPrice = prices[i]; 
      }
      else if (prices[i] > buyingPrice){
        const currProfit = prices[i] - buyingPrice; 
        maxProfit = Math.max(currProfit, maxProfit);
      }
   }

   return maxProfit; 
};

Time Complexity:

• The time complexity is linear, O(N), since we loop over the array once.

Space Complexity:

• The space complexity is constant, any extra space used doesn’t grow as the size of the array N grows.

And like that, we’ve covered two different solutions to the ‘Best Time to Buy and Sell Stock’ problem!

Happy coding!