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`.
### How it works (One Pass approach): Instead of calculating the profit for every possible buy/sell pair (which takes `O(n²)` time), we can do this in a single pass taking `O(n)` time.
1. Maintain two variables: `minPrice` (initialized to infinity) and `maxProfit` (initialized to 0). 2. As we iterate through the days: - If the current price is lower than `minPrice`, update `minPrice`. This represents the best historically cheap day to have bought the stock. - If the current price is *not* lower, calculate the potential profit if we sold today (`currentPrice - minPrice`). - If this potential profit is greater than our recorded `maxProfit`, update `maxProfit`. 3. Return `maxProfit`.
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`.
### How it works (One Pass approach): Instead of calculating the profit for every possible buy/sell pair (which takes `O(n²)` time), we can do this in a single pass taking `O(n)` time.
1. Maintain two variables: `minPrice` (initialized to infinity) and `maxProfit` (initialized to 0). 2. As we iterate through the days: - If the current price is lower than `minPrice`, update `minPrice`. This represents the best historically cheap day to have bought the stock. - If the current price is *not* lower, calculate the potential profit if we sold today (`currentPrice - minPrice`). - If this potential profit is greater than our recorded `maxProfit`, update `maxProfit`. 3. Return `maxProfit`.
Constraints
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^4
TimeO(O(n))
SpaceO(O(1))
Ready to startStep 0 / 0
TypeScript