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 848,237 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] represents the stock price on day i. You must choose one day to buy and a later day to sell. The goal is to maximize profit. If no profitable trade exists, return 0.
Approach 1: Brute Force (For Educational Purposes) (Time: O(n2), Space: O(1))
The straightforward idea checks every possible pair of days. For each day i, treat it as the buy day and iterate through all later days j to compute the profit prices[j] - prices[i]. Track the maximum profit seen during these comparisons. This works because it evaluates every valid buy‑sell combination. However, it requires two nested loops, leading to quadratic time complexity. This approach is mainly useful for understanding the problem before optimizing.
Approach 2: Single Pass with Tracking Minimum Price (Time: O(n), Space: O(1))
The optimal strategy scans the array once while tracking the lowest price seen so far. Think of it as the best buying opportunity up to the current day. At each step, compute the potential profit if you sold today using currentPrice - minPrice. If that profit exceeds the current maximum, update it. Then update minPrice if the current price is lower. This works because the algorithm always ensures the buy happens before the sell while maintaining the best candidate buy price. The result is a linear-time solution with constant memory.
This pattern appears frequently in array problems where you track a running minimum or maximum while scanning once. It can also be interpreted as a simplified form of dynamic programming, where each step maintains the best state (minimum buy price) needed to compute the next profit.
Recommended for interviews: Interviewers expect the single-pass solution. It shows you recognize the key insight: the optimal profit at any day depends only on the lowest price seen earlier. Mentioning the brute force approach first demonstrates problem exploration, but implementing the O(n) scan proves strong algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n^2) | O(1) | Learning phase or verifying logic before optimizing |
| Single Pass with Minimum Price Tracking | O(n) | O(1) | Best general solution; expected in coding interviews |