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.
LeetCode Solutions1 <= prices.length <= 1050 <= prices[i] <= 104We iterate through the prices array exactly once, performing work per element.
Only two variables, min_price and max_profit, are used regardless of input size.
We scan the prices array once, tracking the minimum price seen so far and the maximum profit achievable at each step. For each price, if it is lower than the current minimum we update min_price; otherwise, we compute the profit from buying at min_price and selling today, updating max_profit if it improves. A single pass suffices because any valid sell day already has access to the cheapest buy day before it through min_price.
sell_day advances by one on every iteration and traverses the array at most once, giving total.
Only three integer variables are used, independent of input size.
We maintain two pointers, buy_day and sell_day, starting at indices 0 and 1. If the sell price exceeds the buy price we compute the profit and update max_profit; if not, a cheaper buy opportunity has been found so we advance buy_day to the current position. This correctly tracks the cheapest available buy point because any price lower than the current buy day would already have caused buy_day to move forward.
Two independent linear passes are performed: one to build min_prefix and one to compute the maximum profit, each .
The min_prefix array stores one value per input element, requiring extra space.
We first precompute a min_prefix array where min_prefix[i] holds the minimum price from day 0 through day i. With this array ready, the best profit from selling on day i is simply prices[i] - min_prefix[i], so a second pass finds the overall maximum. Separating the two concerns — finding the cheapest historical buy price and maximizing profit — makes the logic explicit, at the cost of extra space.
We iterate through the prices array once from index 1 to n−1, performing work per step.
Only two variables, current_profit and max_profit, are maintained regardless of input size.
This approach reframes the problem as the maximum subarray sum on the array of daily price changes. By accumulating current_profit using consecutive differences (prices[i] - prices[i-1]), buying on day a and selling on day b is equivalent to summing the differences from a+1 to b — a classic Kadane's observation. Whenever current_profit turns negative, it is reset to 0, representing the decision to start a fresh transaction rather than carry a losing streak forward.
A single pass through the array fills the dp table, performing work per element.
The dp array holds one entry per day, requiring extra space.
We define dp[i] as the maximum profit achievable by selling on or before day i. The recurrence dp[i] = max(dp[i-1], prices[i] - min_price) captures two choices: skip day i and carry forward the best result so far, or sell on day i using the cheapest historical buy price tracked in min_price. The answer is dp[n-1], the best profit over all days.
We iterate through the prices array once, updating both state variables in per step.
Only two scalar state variables, hold and not_hold, are used regardless of input size.
We model the problem with two DP states: hold (the maximum cash after owning a stock) and not_hold (the maximum cash without owning a stock). On each day, hold transitions to the maximum of keeping the current position or buying today (−prices[i]), and not_hold transitions to the maximum of staying idle or selling today (hold + prices[i]). Because we only want one transaction, limiting the buy to the cheapest possible day is naturally captured by always taking max(hold, -prices[i]).
We iterate through the prices array once from index 1 to n−1, performing work per element.
Only two variables, valley and max_profit, are used regardless of input size.
We initialize valley to the first price and scan forward, updating valley whenever a lower price is found and simultaneously checking whether selling today at prices[i] - valley beats the current best profit. Because valley always holds the minimum price seen to the left of any potential sell day, the optimal buy-sell pair is found in a single pass with no extra space.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Greedy (Min Price Tracking) | Intuitive greedy approach, minimal variables | Uses if/elif, so profit update is skipped on the same iteration as a new minimum | |||
| Two Pointers | Explicit buy/sell pointers make intent clear | Slightly more complex than single-variable tracking | |||
| Prefix Minimum Array | Separates concerns clearly, easy to reason about | Requires extra space for the prefix array | |||
| Kadane's Algorithm | Elegant reframe as max subarray sum; generalizes well | Requires understanding the price-difference transformation | |||
| Dynamic Programming | Explicit DP formulation, straightforward to extend | Requires extra space for the dp array | |||
| State Machine DP | Generalizes naturally to multi-transaction variants | Slightly less intuitive for a single-transaction problem | |||
| Valley Tracking (Greedy) | Cleanest code — unconditional updates keep logic minimal | Functionally identical to Solution 1 with only minor stylistic differences |
Both Solution 1: Greedy (Min Price Tracking) and Solution 7: Valley Tracking (Greedy) are optimal, both achieving time complexity and space complexity. They implement the same greedy insight — track the minimum price seen so far and update the best profit simultaneously — with minor stylistic differences: Solution 7 uses unconditional updates and initializes valley from prices[0], making it marginally cleaner, while Solution 1's if/elif structure is equally readable and equally efficient.
class Solution: def maxProfit(self, prices: List[int]) -> int: # Initialize variables to track the minimum price and maximum profit min_price = float('inf') max_profit = 0
for price in prices: if price < min_price: # Update the minimum price if the current price is lower min_price = price elif price - min_price > max_profit: # Update the maximum profit if the current price minus the minimum price is greater than the current maximum profit max_profit = price - min_price
return max_profitclass Solution: def maxProfit(self, prices: List[int]) -> int: buy_day = 0 sell_day = 1 max_profit = 0
# Iterate through the price list with two pointers: buy_day and sell_day while sell_day < len(prices): # If the current sell price is greater than the buy price, calculate profit and update max_profit if prices[buy_day] < prices[sell_day]: profit = prices[sell_day] - prices[buy_day] max_profit = max(max_profit, profit) else: # If the current sell price is less than or equal to the buy price, move the buy_day pointer to the sell_day buy_day = sell_day
sell_day += 1
return max_profitclass Solution: def maxProfit(self, prices: List[int]) -> int: # Prefix array to store the minimum price up to each day min_prefix = [0] * len(prices) min_prefix[0] = prices[0]
# Compute the minimum price up to each day for i in range(1, len(prices)): min_prefix[i] = min(min_prefix[i - 1], prices[i])
max_profit = 0
# Compute the maximum profit by selling on each day for i in range(len(prices)): max_profit = max(max_profit, prices[i] - min_prefix[i])
return max_profitclass Solution: def maxProfit(self, prices: List[int]) -> int: current_profit = 0 max_profit = 0
for i in range(1, len(prices)): # calculate profit for current day and add it to current_profit current_profit += prices[i] - prices[i - 1]
# update max_profit if current_profit is greater, and reset current_profit to 0 if it becomes negative max_profit = max(max_profit, current_profit) current_profit = max(current_profit, 0)
return max_profitclass Solution: def maxProfit(self, prices: List[int]) -> int: min_price = prices[0] dp = [0] * len(prices)
for i in range(1, len(prices)): min_price = min(min_price, prices[i])
# The maximum profit that can be achieved by selling on day i is the maximum of: dp[i] = max(dp[i - 1], prices[i] - min_price)
# The maximum profit that can be achieved by selling on the last day is the answer. return dp[-1]class Solution: def maxProfit(self, prices: List[int]) -> int: hold = -prices[0] # We start with the first price as if we bought the stock on the first day not_hold = 0 # We start with 0 profit as we haven't sold any stock yet
for i in range(1, len(prices)): hold = max(hold, -prices[i]) # We either keep holding the stock or we buy it today (which means we subtract today's price from our profit) not_hold = max(not_hold, hold + prices[i]) # We either keep not holding the stock or we sell it today (which means we add today's price to our profit)
# The maximum profit will be in the not_hold state at the end, as we want to have sold the stock to realize the profit return not_holdclass Solution: def maxProfit(self, prices: List[int]) -> int: valley = prices[0] # We start with the first price as the valley (the lowest price we've seen so far) max_profit = 0 # We start with 0 profit as we haven't sold any stock
for i in range(1, len(prices)): valley = min(valley, prices[i]) # Update the valley if we find a lower price max_profit = max(max_profit, prices[i] - valley) # Update the max profit if we find a higher profit by selling at the current price
# The maximum profit will be the maximum difference between the current price and the lowest price (valley) we've seen so far return max_profit