Stock Buy and Sell – Max one Transaction Allowed

Given an array prices[] of length n, representing the prices of the stocks on different days. The task is to find the maximum profit possible by buying and selling the stocks on different days when at most one transaction is allowed. Here one transaction means 1 buy + 1 Sell. If it is not possible to make a profit then return 0.

Note: Stock must be bought before being sold.

Examples:

Input: prices[] = [7, 10, 1, 3, 6, 9, 2]
Output: 8
Explanation: You can buy the stock on day 2 at price = 1 and sell it on day 5 at price = 9. Hence, the profit is 8.

Input: prices[] = [7, 6, 4, 3, 1]
Output: 0 
Explanation: Here the prices are in decreasing order, hence if we buy any day then we cannot sell it at a greater price. Hence, the answer is 0.

Input: prices[] = [1, 3, 6, 9, 11]
Output: 10 
Explanation: Since the array is sorted in increasing order, we can make maximum profit by buying at price[0] and selling at price[n-1].

Constraint:
1 <= prices.size()<= 10⁵
0 <= prices[i] <=10⁴

Approach 01:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
 public:
  int maximumProfit(vector<int>& stockPrices) {
    int maxProfit = 0;  // To track the maximum profit
    int lowestPrice = stockPrices[0];  // To track the lowest price to buy

    for (int i = 1; i < stockPrices.size(); i++) {
      int currentProfit = 0;

      // If the current price is greater than the lowest price, calculate profit
      if (stockPrices[i] > lowestPrice) {
        lowestPrice = min(lowestPrice, stockPrices[i - 1]);
        currentProfit = stockPrices[i] - lowestPrice;
      } else {
        // Update the lowest price to buy
        lowestPrice = min(lowestPrice, stockPrices[i]);
      }

      // Update the maximum profit
      maxProfit = max(maxProfit, currentProfit);
    }

    return maxProfit;
  }
};

from typing import List

class Solution:
    def maximumProfit(self, stockPrices: List[int]) -> int:
        maxProfit = 0  # To track the maximum profit
        lowestPrice = stockPrices[0]  # To track the lowest price to buy

        for i in range(1, len(stockPrices)):
            currentProfit = 0

            # If the current price is greater than the lowest price, calculate profit
            if stockPrices[i] > lowestPrice:
                lowestPrice = min(lowestPrice, stockPrices[i - 1])
                currentProfit = stockPrices[i] - lowestPrice
            else:
                # Update the lowest price to buy
                lowestPrice = min(lowestPrice, stockPrices[i])

            # Update the maximum profit
            maxProfit = max(maxProfit, currentProfit)

        return maxProfit

Time Complexity

• Iterating Through Stock Prices:

  The function iterates through the stock prices array once, from index 1 to the end. This takes \( O(n) \), where \( n \) is the size of the stockPrices array.

• Updating Values:

  Each iteration involves constant-time operations like comparison, subtraction, and assignment. These do not add to the complexity.

• Overall Time Complexity:

  The overall time complexity is \( O(n) \).

Space Complexity

• Auxiliary Variables:

  Variables like maxProfit, lowestPrice, and currentProfit require \( O(1) \) space.

• Input Array:

  The input array stockPrices is given and does not contribute to additional space usage.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \), as no extra data structures are used.