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.
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.
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.
Time Complexity: O(n^2), where n is the number of days.
Space Complexity: O(1).
We can enumerate each element of the array nums as the selling price. Then we need to find a minimum value in front of it as the purchase price to maximize the profit.
Therefore, we use a variable mi to maintain the prefix minimum value of the array nums. Then we traverse the array nums and for each element v, calculate the difference between it and the minimum value mi in front of it, and update the answer to the maximum of the difference. Then update mi = min(mi, v). Continue to traverse the array nums until the traversal ends.
Finally, return the answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
| 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. |
| Enumerate + Maintain the Minimum Value of the Prefix | — |
| 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 |
Sliding Window: Best Time to Buy and Sell Stock - Leetcode 121 - Python • NeetCode • 1,049,316 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