Best Time to Buy and Sell Stock III - Practice Coding Problems

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

Understanding the Visualization

Input

Array of stock prices over time

Strategy

Find at most 2 transactions for maximum profit

Output

Maximum profit achievable

Key Takeaway

🎯 Key Insight: Use state machine DP to track four transaction states efficiently in one pass

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

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Try all possible combinations of two non-overlapping transactions
State Machine Dynamic Programming	O(n)	O(1)	Track four states: first buy, first sell, second buy, second sell
Two-Pass Dynamic Programming	O(n)	O(n)	Split problem into left and right parts, find best transaction in each

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

⚠ Quadratic 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler