Best time to buy and Sell stock

Easy

Problem

prices[i] is a stock's price on day i. You may buy once and sell once, on a later day. Return the maximum profit you can make, or 0 if no profit is possible.

Example 1

Input:  [7, 1, 5, 3, 6, 4]
Output: 5

Buy on day 1 (price 1), sell on day 4 (price 6).

Example 2

Input:  [7, 6, 4, 3, 1]
Output: 0

Prices only fall, so do not trade.

Test cases

Case 1

Input:    [7,1,5,3,6,4]
Expected: 5

Case 2

Input:    [7,6,4,3,1]
Expected: 0

Case 3

Input:    [5]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. One pass (track min price)

Time O(n)Space O(1)

Keep the lowest price seen so far; the best profit is the largest (price − minSoFar).

function maxProfit(prices) {
let minPrice = Infinity, profit = 0;
for (const p of prices) {
minPrice = Math.min(minPrice, p);
profit = Math.max(profit, p - minPrice);
}
return profit;
}

2. Brute force

Time O(n²)Space O(1)

Try every buy/sell pair. Only useful as the baseline you state before optimising.

function maxProfit(prices) {
let profit = 0;
for (let i = 0; i < prices.length; i++)
for (let j = i + 1; j < prices.length; j++)
profit = Math.max(profit, prices[j] - prices[i]);
return profit;
}