Best time to buy and Sell stock
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
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;}