22. Stock Buy and Sell – Max One Transaction Allowed

The problem can be found at the following link: Problem Link

✨ LeetCode Problem of the Day (POTD) Solutions ✨

• Continuing the LeetCode Problem of the Day (POTD) journey! 🎯

• Today's problem is live: 1072. Flip Columns For Maximum Number of Equal Rows

Problem Description

Given an array prices[] of length n, representing the prices of stocks on different days, find the maximum profit possible by buying and selling the stocks on different days, with at most one transaction allowed (1 buy + 1 sell). If no profit can be made, return 0.

Note: Stocks must be bought before being sold.

Examples:

Input: prices[] = [7, 10, 1, 3, 6, 9, 2] Output: 8

Explanation: Buy the stock on day 2 at price 1 and sell it on day 5 at price 9. Profit is 9 - 1 = 8.

Input: prices[] = [7, 6, 4, 3, 1] Output: 0

Explanation: Prices decrease every day, so no profit is possible.

Input: prices[] = [1, 3, 6, 9, 11] Output: 10

Explanation: Buy on day 1 (price = 1) and sell on the last day (price = 11). Profit is 11 - 1 = 10.

Constraints:

• 1 <= prices.size() <= 10^5

• 0 <= prices[i] <= 10^4

My Approach

1. One Pass Solution:

   • Maintain a buyPrice to track the minimum price seen so far.

   • Track maxProfit by comparing the current price's profit (currentPrice - buyPrice) to the previous maxProfit.

   • Update buyPrice whenever a lower price is encountered.

2. Steps:

   • Start by initializing buyPrice as the first price and maxProfit as 0.

   • Traverse the array and update buyPrice and maxProfit accordingly.

   • The final maxProfit gives the maximum possible profit with one transaction.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n), where n is the size of the array. Only one pass through the array is required.

• Expected Auxiliary Space Complexity: O(1), as the solution uses a constant amount of additional space.

Code (C)

int maximumProfit(int prices[], int pricesSize) {
    int buyPrice = prices[0];
    int maxProfit = 0;

    for (int i = 1; i < pricesSize; i++) {
        if (prices[i] > buyPrice) {
            maxProfit = (maxProfit > prices[i] - buyPrice) ? maxProfit : prices[i] - buyPrice;
        } else {
            buyPrice = prices[i];
        }
    }
    return maxProfit;
}

Code (Cpp)

class Solution {
  public:
    int maximumProfit(vector<int> &prices) {
        int buyPrice = prices[0], maxProfit = 0;

        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > buyPrice) {
                maxProfit = max(maxProfit, prices[i] - buyPrice);
            } else {
                buyPrice = prices[i];
            }
        }
        return maxProfit;
    }
};

Code (Java)

class Solution {
    public int maximumProfit(int prices[]) {
        int buyPrice = prices[0], maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > buyPrice) {
                maxProfit = Math.max(maxProfit, prices[i] - buyPrice);
            } else {
                buyPrice = prices[i];
            }
        }
        return maxProfit;
    }
}

Code (Python)

class Solution:
    def maximumProfit(self, prices):
        buyPrice = prices[0]
        maxProfit = 0

        for i in range(1, len(prices)):
            if prices[i] > buyPrice:
                maxProfit = max(maxProfit, prices[i] - buyPrice)
            else:
                buyPrice = prices[i]

        return maxProfit

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count