Problem Informations

• Problem Index: 121
• Problem Link: Best Time to Buy and Sell Stock
• Topics: Array, Dynamic Programming

Problem Description

You are given an array prices where prices[i] is the price of a given stock on the $i^{th}$ 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 \leq \text{prices.length} \leq 10^5$
• $0 \leq \text{prices}[i] \leq 10^4$

Intuition

The problem asks us to determine the maximum profit achievable by choosing a single day to buy a stock and a different later day to sell it. The challenge lies in maximizing the difference between the selling price and the buying price, given the constraint that the stock must be bought before it is sold. Thus, we are essentially finding the pair of days (buy, sell) such that sell > buy and the profit (prices[sell] - prices[buy]) is maximized.

Approach

To solve this problem, the approach centers around maintaining two pieces of information as we iterate through the prices array: the minimum price observed so far and the maximum profit that can be achieved at each step. The algorithm can be outlined as follows:

1. Initialize a variable max_profit to 0, which will store the maximum profit achievable.
2. Initialize min_price to the first element of the prices array, representing the minimum buying price encountered so far.
3. Iterate over the prices array starting from the second element. For each price:
   • Calculate the potential profit if the stock were sold on the current day. This is done by subtracting the min_price from the current day’s price.
   • Update max_profit to be the maximum of its current value and the potential profit calculated.
   • Update min_price to be the minimum of its current value and the current day’s price to reflect the lowest buying price encountered up to that point.
4. After iterating through the array, max_profit will contain the maximum profit that can be achieved following the rules of the problem.
5. Return max_profit as the result.

This approach efficiently computes the result in a single pass through the array, yielding a time complexity of $O(n)$, where $n$ is the length of the prices array. The space complexity is $O(1)$, as only a fixed number of additional variables are used.

Code

C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0;  // Initialize maximum profit as 0.
        int min_price = prices[0];  // Initialize minimum price as the first day's price.
        
        // Iterate over the prices starting from the second day.
        for (int i = 1; i < prices.size(); ++i) {
            // Calculate the potential profit by selling on day i.
            max_profit = max(max_profit, prices[i] - min_price);
            
            // Update the minimum price if the current price is lower.
            min_price = min(min_price, prices[i]);
        }
        
        // Return the maximum profit achieved.
        return max_profit;
    }
};

Python

class Solution:
    def maxProfit(self, prices):
        max_profit = 0  # Initialize maximum profit as 0.
        min_price = prices[0]  # Initialize minimum price as the first day's price.
        
        # Iterate over the prices starting from the second day.
        for i in range(1, len(prices)):
            # Calculate the potential profit by selling on day i.
            max_profit = max(max_profit, prices[i] - min_price)
            
            # Update the minimum price if the current price is lower.
            min_price = min(min_price, prices[i])
        
        # Return the maximum profit achieved.
        return max_profit

Complexity

• Time complexity: $O(n)$
  The algorithm iterates through the prices array exactly once, which consists of $n$ elements. For each iteration, it performs a constant amount of work involving basic arithmetic and comparison operations. Therefore, the time complexity is linear with respect to the size of the input array, i.e., $O(n)$.

• Space complexity: $O(1)$
  The algorithm uses a constant amount of additional space regardless of the input size. It utilizes a few integer variables (max_profit and min_price) that do not depend on the size of the input array. Thus, the space complexity is constant, i.e., $O(1)$.