Domain 1EasyCORE

Best Time to Buy and Sell Stock

The problem asks us to find the maximum profit that can be achieved by buying and selling a stock on different days. The input is an array `prices` where each element represents the price of the stock on a given day. We need to return the maximum profit possible from a single buy-sell transaction. If no profit can be made, we should return 0.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Dynamic Programming

121. Best Time to Buy and Sell Stock

Model: qwen2.5-coder:14b
Topics: Array,Dynamic Programming
FAANG asked: 1
Acceptance rate: 51.8%


Problem Breakdown

The problem asks us to find the maximum profit that can be achieved by buying and selling a stock on different days. The input is an array prices where each element represents the price of the stock on a given day. We need to return the maximum profit possible from a single buy-sell transaction. If no profit can be made, we should return 0.

Inputs:

  • An array prices of integers representing stock prices over time.

Outputs:

  • An integer representing the maximum profit that can be achieved. If no profit is possible, return 0.

Implicit Constraints or Edge Cases:

  • The array can have a length between 1 and 10^5.
  • Each price in the array is between 0 and 10^4.
  • We cannot sell on the same day we buy.
  • If prices are in strictly decreasing order, the maximum profit is 0.

Intuition

A brute-force approach would involve checking every possible pair of days to see which one yields the highest profit. This would result in a time complexity of O(n^2), which is inefficient given the constraints.

The key insight is that we can keep track of the minimum price encountered so far and calculate the potential profit for each day by subtracting this minimum price from the current day’s price. By doing this, we ensure that we are always buying at the lowest possible price seen up to that point and selling on the current day.

Approach

  1. Initialize two variables: min_price to a very high value (e.g., infinity) and max_profit to 0.
  2. Iterate through each price in the array:
    • Update min_price to be the minimum of the current min_price and the current day’s price.
    • Calculate the potential profit by subtracting min_price from the current day’s price.
    • Update max_profit to be the maximum of the current max_profit and the calculated potential profit.
  3. After iterating through all prices, return max_profit.

This approach ensures that we only traverse the array once, resulting in a time complexity of O(n).

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the prices array. We make a single pass through the array.
  • Space Complexity: O(1). We use a constant amount of extra space for variables.

Solution

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0
    
    for price in prices:
        min_price = min(min_price, price)
        potential_profit = price - min_price
        max_profit = max(max_profit, potential_profit)
    
    return max_profit

Edge Cases Handled

  • Empty Input: The function will handle an empty input array by returning 0 since max_profit is initialized to 0.
  • All Prices Increasing: If the prices are in strictly increasing order, the maximum profit will be the difference between the last and first price.
  • All Prices Decreasing: If the prices are in strictly decreasing order, the minimum price will always be updated to the current price, resulting in a max_profit of 0.
  • Single Price: If there is only one price in the array, the function will return 0 as no transaction can be made.

The solution provided is correct and efficient. It adheres to the constraints and handles all edge cases appropriately. The time complexity is O(n), which is optimal for this problem, and the space complexity is O(1), as expected.