Problem Statement

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.

Examples

1. • Input: [3, 2, 6, 5, 0, 3]
   • Expected Output: 4
   • Justification: Buy the stock on day 2 (price = 2) and sell it on day 3 (price = 6). Profit = 6 - 2 = 4.
2. • Input: [8, 6, 5, 2, 1]
   • Expected Output: 0

• Justification: Prices are continuously dropping, so no profit can be made.

3. • Input: [1, 2]
   • Expected Output: 1
   • Justification: Buy on day 1 (price = 1) and sell on day 2 (price = 2). Profit = 2 - 1 = 1.

Constraints:

• 1 <= prices.length <= 10⁵
• 0 <= prices[i] <= 10⁴

Solution

To solve this problem, we iterate through the list of stock prices to find the maximum profit that can be made by buying and selling once. The approach involves keeping track of the lowest price seen so far and calculating the potential profit if the stock were sold at the current price. As we continue to iterate through the prices, we consistently update the minimum price and the maximum profit observed. By the end of the loop, we have determined the highest possible profit that can be achieved from a single buy-sell transaction, ensuring an efficient solution with linear time complexity.

Step-by-Step Algorithm

1. Initialize Variables:

   • Set a variable to hold the minimum price encountered so far to a very high value (initially, the maximum possible integer value).
   • Set a variable to hold the maximum profit calculated so far to 0.

2. Iterate Through Each Price in the Array:

   • For each price in the given array:
     • Update the Minimum Price:
       • Compare the current price with the minimum price encountered so far.
       • If the current price is lower, update the minimum price to the current price.
     • Calculate the Potential Profit:
       • Subtract the updated minimum price from the current price to calculate the potential profit if selling at this price.
     • Update the Maximum Profit:
       • Compare the calculated potential profit with the maximum profit recorded so far.
       • If the potential profit is higher, update the maximum profit to this value.

3. Return the Maximum Profit:

   • After completing the iteration through all prices, return the maximum profit calculated.

Algorithm Walkthrough

Consider the input [3, 2, 6, 5, 0, 3]:

• Initialize minPrice as infinity and maxProfit as 0.
• Iterate through the list:
  • Day 1: price is 3
    • minPrice is updated to 3.
    • Profit = 3 - 3 = 0. maxProfit remains 0.
  • Day 2: price is 2
    • minPrice is updated to 2.
    • Profit = 2 - 2 = 0. maxProfit remains 0.
  • Day 3: price is 6
    • minPrice remains 2.
    • Profit = 6 - 2 = 4. maxProfit is updated to 4.
  • Day 4: price is 5
    • minPrice remains 2.
    • Profit = 5 - 2 = 3. maxProfit remains 4.
  • Day 5: price is 0
    • minPrice is updated to 0.
    • Profit = 0 - 0 = 0. maxProfit remains 4.
  • Day 6: price is 3
    • minPrice remains 0.
    • Profit = 3 - 0 = 3. maxProfit remains 4.
• The final maxProfit is 4.

Code

Complexity Analysis

• Time Complexity: O(n), where n is the number of days. This is because the algorithm iterates through the list of prices once, performing constant-time operations for each price.
• Space Complexity: O(1), as it uses a constant amount of extra space (two variables to keep track of minPrice and maxProfit).