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.
In this approach, we traverse the prices array while keeping track of the minimum price seen so far and calculate the maximum profit we could achieve if we sold on that day. The maximum profit is updated accordingly through each iteration.
This approach makes a single pass through the array (O(n) time complexity) and uses constant space (O(1) space complexity).
This C solution iterates through the given prices array. It maintains the minimum price found so far and calculates potential profit as the difference between the current day's price and the tracked minimum price. The maximum of this profit value is retained.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of days.
Space Complexity: O(1).
This approach considers all possible pairs of buy and sell days, calculating the profit for each combination. It is straightforward but inefficient due to its O(n^2) time complexity, which is impractical for large inputs.
This C implementation uses nested loops to check all possible buy and sell day pairs, computing the profit and tracking the highest encountered. It serves as an illustration of the brute force method.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where n is the number of days.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Single Pass with Tracking Minimum Price | Time Complexity: O(n), where n is the number of days. |
| Approach 2: Brute Force (For Educational Purposes) | Time Complexity: O(n^2), where n is the number of days. |
| 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 |
Sliding Window: Best Time to Buy and Sell Stock - Leetcode 121 - Python • NeetCode • 848,237 views views
Watch 9 more video solutions →Practice Best Time to Buy and Sell Stock with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor