Best Time to Buy and Sell Stock
You start day trading while working as a remote software engineer, and you realize that you may have found a strategy that will allow you to make tons of money by going against hedge funds. You realize this strategy will require you to hodl for multiple days to realize the largest profit, so you know that you will need diamond hands 💎🙌. In order to backtest this strategy, you want to see the maximum you could have earned by buying at the lowest point and selling at the highest point.
Write a function getMaxProfit that takes an array of stock prices ordered sequentially by day and returns the max profit you could earn by buying and selling at the optimal time.
You never want to lose money, so if there is no max profit, return 0.
Since these are stock prices, we will assume the items in the array will all be positive integers.
 Breakdown
Approach and test strategy
A running minimum with a forward-only buy/sell order
Read the approach, boundary cases, and complexity
Choose at most one purchase followed by one sale. Scan prices in chronological order, retaining the smallest earlier purchase price and the best profit found so far. A globally smallest and globally largest price do not form a valid trade when their order is reversed. Initialize the no-trade result to zero so falling prices do not force a loss.
Cases to check
- Empty input and one price both return zero.
- For [9, 2, 4, 3, 8, 5], the best profit is six.
- Test decreasing prices, repeated prices, and a late new minimum before a larger sale.
Cost model
One scan uses O(n) time and O(1) auxiliary state. Use arithmetic that can represent the allowed price differences.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
Validate My Answer
You may be tempted to find the difference between the smallest and largest value in the input stock price array. Since these prices are listed sequentially by day, this solution may produce results where you buy in the future and sell in the past. This is impossible, at least until we invent time travel.
The brute force solution is O(n2) but you can do better.
The optimal solution can solve this question in O(n) time and O(1) space where we only iterate through the input array once.
This question has many edge cases, so make sure you handle those. For example: prices always decreasing, prices always increasing, empty input array, single price input array, etc.
Best Time to Buy and Sell Stock
You start day trading while working as a remote software engineer, and you realize that you may have found a strategy that will allow you to make tons of money by going against hedge funds. You realize this strategy will require you to hodl for multiple days to realize the largest profit, so you know that you will need diamond hands 💎🙌. In order to backtest this strategy, you want to see the maximum you could have earned by buying at the lowest point and selling at the highest point.
Write a function getMaxProfit that takes an array of stock prices ordered sequentially by day and returns the max profit you could earn by buying and selling at the optimal time.
You never want to lose money, so if there is no max profit, return 0.
Since these are stock prices, we will assume the items in the array will all be positive integers.
Â