The Problem

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. 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

Given

You are given array of numbers is given. Each number represents the price of a stock on a given day. The indices of these number can be thought of as a timeline of days.

Return

Return a number representing the maximum profit that can be made by buying a stock one day and selling it another day. This number will be greatest difference between two values in the array where the value with the higher index has the higher value.

Problem Solving Strategy

The array will need to be iterated through and two values will need to be compared at every iteration. At every iteration, the value with a lower index will be subtracted from the value with the higher index. This will give you the current profit, which represents the profit you get when buying and selling at those two days. There will also need to be a running maximum profit stored. At each iteration, the current profit will be compared to the maximum profit. If it is a greater number, it's value can now become the maximum profit value. Once the loop has finished, the value stored in the maximum profit variable will be the maximum profit and it can be returned. However, a single loop will only allow you track a single value at every iteration and we need two values. The only challenge left is figuring out how to loop through the array in a way that ensures the two values that create the maximum profit are found at the same time.

function buyAndSellStocks(array) {
  let greatestDiff = 0
  for (let i = 0; i < array.length - 1; i++) {
    for (let j = i + 1; j < array.length; j++) {
      let currentDiff = array[j] - array[i]
      if (currentDiff > greatestDiff) greatestDiff = currentDiff
    }
  }
  return greatestDiff
}

Approach One (Brute Force)

One way to do this is nest another loop within the loop. This allows us to look through all values that come after our current value and see if the difference between them is greater than the current maximum. By the end of the loop, this approach will have looked through every single combination of values. Therefore, it guarantees the maximum profit is found at some point and it will return the correct answer. But, does every single combination of numbers need to be checked or is there a more efficient way to navigate the array? This approach runs in O(N^2) where is the length of the array because of the nested loop. It is possible to do better.

Approach Two (Tracking The Minimum)

In approach one, the only data we store throughout the loop is the maximum profit. What if we also stored the minimum value? The day where the stock price is lowest will always be the best day to buy. We can use this knowledge to know that we don't need to grab two values at each iteration. We just need to compare our current value with lowest value. To do this, we just need to add an extra step to ensure we are tracking the lowest value. There are a few ways to do this. First we initialize it to zero, since the problem states "if you cannot achieve any profit, return 0". Since we are already calculating the maximum profit at every iteration, we can just use this to check when we hit a new minimum value value. The current profit in this approach will be calculated by subtracting the running minimum from the current value. Similar to the other approach, the current profit will be compared to the maximum profit to see if it should replace it. But, we can now use our current profit for a secondary purpose. If profit is negative at an iteration, we know that our current value is lower than the running minimum value and can therefore take its place as the new minimum. These calculations ensure we have the proper maximum profit and the proper minimum value every step of the way. This runs in O(N) time since the single for loop is now the only factor affecting time complexity. Both approaches run in constant space. Both approaches store the maximum profit and approach two also stores the minimum value. The are both constant space since they do not depend on the input.

function buyAndSellStocks2(array) {
  let current = array[0] 
  let greatestDiff = 0 
  for (let value of array) { 
    let currentDiff = value - current 
    if (currentDiff < 0) current = value 
    if (currentDiff > greatestDiff) greatestDiff = currentDiff 
  }
  return greatestDiff
}