Best Time to Buy and Sell Stock
Question link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
Problem: Best Time to Buy and Sell Stock
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.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 104
Walkthrough
The problem asks us to find the best day to buy stock and the best day to sell it. As the saying goes, buy low, sell high. As usual let’s try to find a solution using plain English.
Working out the logic in plain English
- We’d need to loop through the list
- Keep track of the previous values and then subtracting the future values from it to find profit
- Find highest profit and return it
The above is a simple English solution, i.e. if you were to tell a 5 year old to do this task by hand using the above instructions, they might be able to solve it.
A tweak to the above algorithm is that we do NOT need to keep track of all the previous values, we only need to keep track of the minimum values as that’s the day that we should buy from.
Therefore here is our new tweaked algorithm in plain English
- We’d need to loop through the list
- Keep track of the previous minimum values and then subtracting the future values from it to find profit
- Find highest profit and return it
Converting English logic to code
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
// keep track of the highest profit and smallest value
let maxProfit = 0
let minVal = prices[0]
for (let price of prices) {
let profit = price - minVal
// if profit is greater than what we've stored, that's the max profit
if (profit > maxProfit) {
maxProfit = profit
}
// if in the future we've found a value thats smaller than our minVal, replace minVal
if (price < minVal) {
minVal = price
}
}
return maxProfit
};
Analysis
Time Complexity
We are looping through the prices list once, making it’s time complexity O(n) .
Space Complexity
We are only storing a constant amount of data so it’s space complexity is O(1) .