JavaScript: Stock Prices Problem
Problem: Write a function that takes an array of stock prices and returns the best profit you could make from one purchase and one sale.
For example:
const prices = [10, 6, 3, 9, 11, 5];
maxProfit(prices);
// returns 8 (buying for $3 and selling for $11)
Brute Force Solution
Try every pair of times treating the earlier time as buy time and the later time as sell time, and see which one is higher.
// O(n^2) time
function maxProfit(prices) {
let maxProfit = 0;
for (let i=0; i < prices.length; i++) {
for (let j=0; j < prices.length; j++) {
let earlierTime = Math.min(i, j);
let laterTime = Math.max(i, j);
let earlierPrice = prices[earlierTime];
let laterPrice = prices[laterTime];
let potentialProfit = laterPrice - earlierPrice;
maxProfit = Math.max(maxProfit, potentialProfit);
}
}
return maxProfit;
}
One problem: you can never have a negative profit!
Better Solution
We have to compare every price so O(n) is the best we can do. Let’s take a greedy approach by keeping a running maxProfit
until the end. So for every price check if:
- we can get a better profit by buying at
minPrice
and selling atcurrentPrice
- we can have a new
minPrice
Initialize maxProfit
as the first profit we could get, not 0
.
// O(n) time & O(1) space
function maxProfit(prices) {
let minPrice = prices[0];
let maxProfit = prices[1] - prices[0];
for (let i = 1; i < prices.length; i++) {
let currentPrice = prices[i];
let potentialProfit = currentPrice - minPrice;
maxProfit = Math.max(maxProfit, potentialProfit);
minPrice = Math.min(minPrice, currentPrice);
}
return maxProfit;
}
Want to improve your JavaScript? I have a list of recommended JavaScript books.