121. Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Problem

Example

Solution O(n^2)

This is extremely trivial and terribly slow. The most straightforward strategy is to go through the stock prices, and for each stock price you subtract the other stock prices from itself and store that difference in a list of returns. From there, we can find the highest by finding the maximum return, which is the highest profit!

Solution O(n), one-pass!

In order to derive an O(n) solution, we need to look at the requirements of the problem; that is what we are taking in, and what we are outputting at the end. In this case, our function receives an array input, and is only required to return the maximum profit obtainable - without a specification on which items yielded that profit (or in other words, which day the stock was bought and sold).

Knowing this, I could break the problem down and analyse what was happening at each step. Looking at the example, I notice to obtain the profit, I simply took the stocks ahead of the current parent stock I was tracking (i) and subtracted them.

The distinction then begins here. If I were to determine the profit was negative, then I KNOW for certain that the second stock (j) is SMALLER than the parent stock (i) - meaning, there is an opportunity for greater profit with the second stock. Therefore, I would much rather have the second stock replace my current parent stock if the difference is negative as my interest lies in minimising the initial cost (price of parent) and maximising the latter price (in this case denoted as j).

Going through it once, my rules are then defined by the result of the difference, which tells me whether or not I should invest in a lower costing stock.

This example makes sense and translates to real life as you would much rather wait for the stock to be at its LOWEST price because then you can only profit from there!