Coding problem · Easy · Sliding Window
Best Time to Buy and Sell Stock
Easy Algorithms & data structures Most askedSeen at Amazon, Meta, Bloomberg, Goldman Sachs
You are given an array prices where prices[i] is a stock's price on day i. Choose one day to buy and a later day to sell to maximize profit. Return the maximum profit, or 0 if no profit is possible.
Example 1
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy at 1, sell at 6.
Example 2
Input: prices = [7,6,4,3,1] Output: 0
Constraints
1 <= prices.length <= 10^5
Hints
Hint 1
Track the lowest price seen so far; each day, the best sale is today's price minus that minimum.
Write and run your solution
Loading the editor… (JavaScript is required to run code in your browser.)
Solution and explanation
Show the solution
Time O(n) · Space O(1)
Keep the minimum price so far (the best buy day in the window) and the best profit price - min. One pass, constant space.
Reference solution
function maxProfit(prices) {
let min = Infinity, best = 0;
for (const p of prices) {
min = Math.min(min, p);
best = Math.max(best, p - min);
}
return best;
}
function maxProfit(prices: number[]): number {
let min = Infinity, best = 0;
for (const p of prices) {
min = Math.min(min, p);
best = Math.max(best, p - min);
}
return best;
}
def max_profit(prices: list[int]) -> int:
low, best = float("inf"), 0
for p in prices:
low = min(low, p)
best = max(best, p - low)
return best
<?php
function maxProfit(array $prices): int
{
$min = PHP_INT_MAX;
$best = 0;
foreach ($prices as $p) {
$min = min($min, $p);
$best = max($best, $p - $min);
}
return $best;
}
class Solution {
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE, best = 0;
for (int p : prices) {
min = Math.min(min, p);
best = Math.max(best, p - min);
}
return best;
}
}
Follow-up questions
- Unlimited transactions? (sum every positive daily gain)
- At most two transactions? (DP with four states)