Watch 10 video solutions for Best Time to Buy and Sell Stock, a easy level problem involving Array, Dynamic Programming. This walkthrough by NeetCode has 1,049,316 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 104Problem Overview: You are given an array where prices[i] is the stock price on day i. You must choose one day to buy and a later day to sell to maximize profit. If no profitable transaction exists, return 0.
Approach 1: Brute Force (O(n²) time, O(1) space)
The straightforward solution checks every possible pair of days. For each day i, treat it as the buying day and compare it with every later day j as the selling day. Compute the profit prices[j] - prices[i] and track the maximum value. This approach uses nested loops over the array, so the time complexity grows quadratically. It works for small inputs and helps verify the logic of the problem, but becomes slow for large datasets.
Approach 2: Single Pass with Tracking Minimum Price (O(n) time, O(1) space)
The optimal solution scans the array once while maintaining the lowest price seen so far. At each step, treat the current price as a potential selling price and compute the profit using currentPrice - minPrice. If this profit exceeds the best profit recorded so far, update the result. Otherwise, update minPrice when a lower price appears. This works because the best transaction must buy at the lowest price before the sell day.
This technique resembles a simplified dynamic programming or greedy strategy: maintain state (minPrice) while iterating through the array and update the best answer incrementally. Only two variables are required, so space usage stays constant. The algorithm performs exactly one pass over the data, making it efficient even for very large inputs.
Recommended for interviews: Interviewers expect the single-pass minimum tracking approach. The brute force solution demonstrates baseline reasoning and correctness, but the O(n) scan shows you recognize the key insight: the best sell decision depends only on the smallest price seen before that day. Implementing this efficiently with constant space is the standard interview solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Check All Buy/Sell Pairs) | O(n²) | O(1) | Educational baseline to understand profit calculation and validate logic |
| Single Pass with Minimum Price Tracking | O(n) | O(1) | Optimal solution for interviews and production; handles large arrays efficiently |