20. Stock Buy and Sell – Max 2 Transactions Allowed

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

Problem Description

In daily share trading, a trader buys shares and sells them on the same day. Given an array prices[] representing stock prices throughout the day, find the maximum profit a trader could have made with at most 2 transactions.

⚠ Note: The second transaction can only start after the first one is complete (buy β†’ sell β†’ buy β†’ sell).

Examples

Example 1:

Input:

prices[] = [10, 22, 5, 75, 65, 80]

Output:

87

Explanation:

  • Buy at 10, sell at 22 β†’ Profit = 12

  • Buy at 5, sell at 80 β†’ Profit = 75

  • Total Profit = 12 + 75 = 87

Example 2:

Input:

prices[] = [2, 30, 15, 10, 8, 25, 80]

Output:

100

Explanation:

  • Buy at 2, sell at 30 β†’ Profit = 28

  • Buy at 8, sell at 80 β†’ Profit = 72

  • Total Profit = 28 + 72 = 100

Constraints:

  • $1 \leq \text{prices.size()} \leq 10^5$

  • $1 \leq \text{prices[i]} \leq 10^5$

My Approach

Optimized Greedy Approach

  1. Use four variables:

    • b1 (Best price to buy first stock)

    • s1 (Best profit after first sale)

    • b2 (Best price to buy second stock after first sale)

    • s2 (Best profit after second sale)

  2. Iterate through prices and update these variables accordingly.

  3. Return s2 (Maximum profit with at most two transactions).

Algorithm Steps:

  1. Initialize b1 = ∞, s1 = 0, b2 = ∞, s2 = 0.

  2. For each price p in the array:

    • Update b1 (Minimum price to buy first stock).

    • Update s1 (Best profit after first sale).

    • Update b2 (Best price to buy second stock).

    • Update s2 (Best profit after second sale).

  3. Return s2.

Time and Auxiliary Space Complexity

  • Expected Time Complexity: O(N), as we traverse the array once and perform a constant number of operations.

  • Expected Auxiliary Space Complexity: O(1), as we use only four variables.

Code (C++)

class Solution {
  public:
    int maxProfit(vector<int>& a) {
        int b1 = INT_MAX, s1 = 0, b2 = INT_MAX, s2 = 0;
        for (int p : a) {
            b1 = min(b1, p);
            s1 = max(s1, p - b1);
            b2 = min(b2, p - s1);
            s2 = max(s2, p - b2);
        }
        return s2;
    }
};
⚑ Alternative Approaches

1️⃣ Dynamic Programming (O(N) Time, O(N) Space)

Algorithm Steps:

  1. Define a dp[i][j] table where dp[i][j] represents the maximum profit achievable up to day i with j transactions.

  2. Recurrence Relation: $[ dp[i][j] = \max(dp[i-1][j], \max_{k=0}^{i-1} (prices[i] - prices[k] + dp[k][j-1])) ]$

  3. Use a space-optimized 1D DP array to reduce O(NΒ²) complexity to O(N).

class Solution {
  public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        vector<vector<int>> dp(3, vector<int>(prices.size(), 0));
        for (int t = 1; t <= 2; t++) {
            int maxDiff = -prices[0];
            for (int d = 1; d < prices.size(); d++) {
                dp[t][d] = max(dp[t][d-1], prices[d] + maxDiff);
                maxDiff = max(maxDiff, dp[t-1][d] - prices[d]);
            }
        }
        return dp[2][prices.size()-1];
    }
};

βœ… Time Complexity: O(N) βœ… Space Complexity: O(N)

2️⃣ Greedy + Prefix/Suffix Array (O(N) Time, O(N) Space)

Algorithm Steps:

  1. Use prefix max profit (left[i]) to track max profit from 0 to i.

  2. Use suffix max profit (right[i]) to track max profit from i to N-1.

  3. Merge results to get the maximum of left[i] + right[i+1].

class Solution {
  public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int n = prices.size();
        vector<int> left(n, 0), right(n, 0);

        int minPrice = prices[0], maxProfit = 0;
        for (int i = 1; i < n; i++) {
            minPrice = min(minPrice, prices[i]);
            left[i] = max(left[i-1], prices[i] - minPrice);
        }

        int maxPrice = prices[n-1];
        for (int i = n-2; i >= 0; i--) {
            maxPrice = max(maxPrice, prices[i]);
            right[i] = max(right[i+1], maxPrice - prices[i]);
        }

        for (int i = 0; i < n; i++)
            maxProfit = max(maxProfit, left[i] + right[i]);

        return maxProfit;
    }
};

βœ… Time Complexity: O(N) βœ… Space Complexity: O(N)

3️⃣ Recursive + Memoization (O(N) Time, O(NΓ—2) Space)

Algorithm Steps:

  1. Use a recursive function maxProfit(index, transactions, holding) that computes:

    • If you are holding a stock, you can sell or keep it.

    • If you don't have a stock, you can buy or skip.

  2. Memoization (dp[i][j][h]):

    • i: Day index.

    • j: Transactions used (max 2).

    • h: Holding status (0 or 1).

class Solution {
  public:
    int dp[100005][3][2];

    int solve(vector<int>& prices, int i, int t, int h) {
        if (i == prices.size() || t == 0) return 0;
        if (dp[i][t][h] != -1) return dp[i][t][h];

        int doNothing = solve(prices, i + 1, t, h);
        int doTrade = h ? (prices[i] + solve(prices, i + 1, t - 1, 0)) : (-prices[i] + solve(prices, i + 1, t, 1));

        return dp[i][t][h] = max(doNothing, doTrade);
    }

    int maxProfit(vector<int>& prices) {
        memset(dp, -1, sizeof(dp));
        return solve(prices, 0, 2, 0);
    }
};

βœ… Time Complexity: O(N) βœ… Space Complexity: O(NΓ—2)

Comparison of Approaches

Approach

⏱️ Time Complexity

πŸ—‚οΈ Space Complexity

βœ… Pros

⚠️ Cons

Greedy (Optimized)

🟒 O(N)

🟒 O(1)

Best for large inputs

Hard to intuitively understand

DP (2D Table)

🟒 O(N)

πŸ”΄ O(N)

Easy to implement, intuitive

Higher space usage

Prefix-Suffix Arrays

🟒 O(N)

🟑 O(N)

Easier to understand

Extra space usage

Recursive + Memoization

🟒 O(N)

πŸ”΄ O(NΓ—2)

Intuitive recursion approach

High memory usage

βœ… Best Choice?

  • If you want best efficiency: Use Greedy (Optimized) approach.

  • If you prefer DP-style tabulation: Use 2D DP Approach.

  • If you like prefix-suffix tricks: Use Prefix-Suffix Arrays.

  • If you like recursion: Use Recursive + Memoization.

Code (Java)

class Solution {
    public static int maxProfit(int[] a) {
        int b1 = Integer.MAX_VALUE, s1 = 0, b2 = Integer.MAX_VALUE, s2 = 0;
        for (int p : a) {
            b1 = Math.min(b1, p);
            s1 = Math.max(s1, p - b1);
            b2 = Math.min(b2, p - s1);
            s2 = Math.max(s2, p - b2);
        }
        return s2;
    }
}

Code (Python)

class Solution:
    def maxProfit(self, a):
        b1, s1, b2, s2 = float('inf'), 0, float('inf'), 0
        for p in a:
            b1, s1, b2, s2 = min(b1, p), max(s1, p - b1), min(b2, p - s1), max(s2, p - b2)
        return s2

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

Last updated