Best Time to Buy and Sell Stock III - Problem

You are given an array prices where prices[i] is the price of a given stock on the i-th day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Input & Output

Example 1 — Two Profitable Transactions

$ Input: prices = [3,3,5,0,0,3,1,4]

› Output: 6

💡 Note: Buy on day 4 (price = 0) and sell on day 6 (price = 1), profit = 1. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 3. Total profit = 1 + 3 = 4. Wait, actually: buy on day 0 (price = 3), sell on day 2 (price = 5), profit = 2. Buy on day 3 (price = 0), sell on day 5 (price = 3), profit = 3. Total = 2 + 3 = 5. Actually the optimal is: buy day 3 (price=0), sell day 5 (price=3), profit=3. Buy day 6 (price=1), sell day 7 (price=4), profit=3. Total = 6.

Example 2 — One Transaction Better

$ Input: prices = [1,2,3,4,5]

› Output: 4

💡 Note: Buy on day 0 (price = 1) and sell on day 4 (price = 5), profit = 4. Since prices are monotonically increasing, one transaction is optimal.

Example 3 — No Profit Possible

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

› Output: 0

💡 Note: Prices are monotonically decreasing, so no profitable transaction is possible.

Constraints

1 ≤ prices.length ≤ 10⁵
0 ≤ prices[i] ≤ 10⁵

Visualization

Tap to expand

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to model this as a state machine with four states representing transaction progress. The optimal approach uses dynamic programming to track buy1, sell1, buy2, sell2 states in a single pass. Time: O(n), Space: O(1).

Common Approaches

✓ Brute Force

⏱️ Time: O(n³) Space: O(1)

For each possible first transaction (buy day i, sell day j), find the best second transaction from remaining days. This explores all valid combinations of two transactions.

State Machine Dynamic Programming

⏱️ Time: O(n) Space: O(1)

Models the problem as a state machine with four states representing transaction progress. At each day, update all states based on current price and previous optimal values.

Two-Pass Dynamic Programming

⏱️ Time: O(n) Space: O(n)

First pass finds maximum profit from single transaction ending on or before each day. Second pass finds maximum profit from single transaction starting on or after each day. Combine both for optimal split point.

Brute Force — Algorithm Steps

Iterate through all possible first buy days
For each first buy, try all possible first sell days
For each first transaction, find optimal second transaction in remaining days
Track maximum profit across all combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

First Transaction

Try all possible buy-sell pairs

Second Transaction

For each first transaction, try all remaining pairs

Maximum

Track the best combined profit

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* prices, int size) {
    if (size < 2) return 0;
    
    int maxProfit = 0;
    
    // Try all possible first transactions
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            int firstProfit = prices[j] - prices[i];
            
            // Find best second transaction after day j
            int secondProfit = 0;
            for (int k = j + 1; k < size; k++) {
                for (int l = k + 1; l < size; l++) {
                    int profit = prices[l] - prices[k];
                    if (profit > secondProfit) {
                        secondProfit = profit;
                    }
                }
            }
            
            int totalProfit = firstProfit + secondProfit;
            if (totalProfit > maxProfit) {
                maxProfit = totalProfit;
            }
        }
    }
    
    // Also try single transaction
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            int profit = prices[j] - prices[i];
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }
    }
    
    return maxProfit;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int prices[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        prices[size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(prices, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops: first buy day, first sell day, and finding best second transaction

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track maximum profit

✓ Linear Space

95.0K Views

High Frequency

~25 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Best Time to Buy and Sell Stock III - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler