Buy and Sell Stocks All Variants in DSA C++

Mental Model

We want to find the best times to buy and sell stocks to maximize profit by looking at price changes over days.

Analogy: Imagine you are a fruit seller buying fruits at low prices and selling them at high prices on different days to earn the most money.

Day:    0    1    2    3    4    5
Price:  7 ->  1 ->  5 ->  3 ->  6 ->  4
Buy:   ↑
Sell:        ↑

Dry Run Walkthrough

Input: prices = [7, 1, 5, 3, 6, 4], max 1 transaction

Goal: Find the best single buy and sell day to maximize profit

Step 1: Set min_price to first price 7, max_profit to 0

min_price=7, max_profit=0

Why: Start tracking lowest price and profit

Step 2: Check price 1: update min_price to 1 (lower than 7)

min_price=1, max_profit=0

Why: Found a cheaper day to buy

Step 3: Check price 5: profit = 5 - 1 = 4, update max_profit to 4

min_price=1, max_profit=4

Why: Selling at 5 after buying at 1 gives better profit

Step 4: Check price 3: profit = 3 - 1 = 2, max_profit stays 4

min_price=1, max_profit=4

Why: Profit less than max, no update

Step 5: Check price 6: profit = 6 - 1 = 5, update max_profit to 5

min_price=1, max_profit=5

Why: Better profit found

Step 6: Check price 4: profit = 4 - 1 = 3, max_profit stays 5

min_price=1, max_profit=5

Why: Profit less than max, no update

Result:

max_profit = 5 (buy at 1, sell at 6)

Annotated Code

DSA C++

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

// Variant 1: Max profit with only one transaction
int maxProfitOneTransaction(const vector<int>& prices) {
    int min_price = INT_MAX;
    int max_profit = 0;
    for (int price : prices) {
        if (price < min_price) {
            min_price = price; // update min price
        } else if (price - min_price > max_profit) {
            max_profit = price - min_price; // update max profit
        }
    }
    return max_profit;
}

// Variant 2: Max profit with unlimited transactions
int maxProfitUnlimitedTransactions(const vector<int>& prices) {
    int max_profit = 0;
    for (size_t i = 1; i < prices.size(); ++i) {
        if (prices[i] > prices[i - 1]) {
            max_profit += prices[i] - prices[i - 1]; // add all positive differences
        }
    }
    return max_profit;
}

// Variant 3: Max profit with at most two transactions
int maxProfitTwoTransactions(const vector<int>& prices) {
    int n = prices.size();
    if (n == 0) return 0;
    vector<int> left_profits(n, 0);
    vector<int> right_profits(n + 1, 0);

    int min_price = prices[0];
    for (int i = 1; i < n; ++i) {
        min_price = min(min_price, prices[i]); // track min price from left
        left_profits[i] = max(left_profits[i - 1], prices[i] - min_price); // max profit left
    }

    int max_price = prices[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        max_price = max(max_price, prices[i]); // track max price from right
        right_profits[i] = max(right_profits[i + 1], max_price - prices[i]); // max profit right
    }

    int max_profit = 0;
    for (int i = 0; i < n; ++i) {
        max_profit = max(max_profit, left_profits[i] + right_profits[i + 1]); // combine
    }
    return max_profit;
}

int main() {
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    cout << "Max profit with one transaction: " << maxProfitOneTransaction(prices) << "\n";
    cout << "Max profit with unlimited transactions: " << maxProfitUnlimitedTransactions(prices) << "\n";
    cout << "Max profit with at most two transactions: " << maxProfitTwoTransactions(prices) << "\n";
    return 0;
}

if (price < min_price) { min_price = price; // update min price }

update min price to find best buy day

else if (price - min_price > max_profit) { max_profit = price - min_price; // update max profit }

update max profit if selling today is better

for (size_t i = 1; i < prices.size(); ++i) { if (prices[i] > prices[i - 1]) { max_profit += prices[i] - prices[i - 1]; // add all positive differences } }

sum all positive price differences for unlimited transactions

min_price = min(min_price, prices[i]); left_profits[i] = max(left_profits[i - 1], prices[i] - min_price);

compute max profit from left side with one transaction

max_price = max(max_price, prices[i]); right_profits[i] = max(right_profits[i + 1], max_price - prices[i]);

compute max profit from right side with one transaction

max_profit = max(max_profit, left_profits[i] + right_profits[i + 1]);

combine left and right profits for two transactions

Output

Max profit with one transaction: 5

Max profit with unlimited transactions: 7

Max profit with at most two transactions: 7

Complexity Analysis

Time: O(n) because we scan the price list a few times linearly

Space: O(n) for the two arrays used in the two transactions variant

vs Alternative: Naive approach tries all pairs or triplets of days with O(n^2) or O(n^3), which is much slower

Edge Cases

empty price list

returns 0 profit because no transactions possible

DSA C++

if (n == 0) return 0;

prices always decreasing

max profit remains 0 because no profitable transaction

DSA C++

max_profit initialized to 0 and never updated

prices constant

max profit remains 0 because no gain from buying and selling

DSA C++

max_profit initialized to 0 and never updated

When to Use This Pattern

When you see a problem asking for maximum profit from stock prices with constraints on transactions, use buy and sell stock patterns to track min prices and profits efficiently.

Common Mistakes

Mistake: Trying to check all pairs of buy and sell days leading to O(n^2) time
Fix: Use one pass tracking min price and max profit or dynamic programming for multiple transactions

Mistake: Adding profits from overlapping transactions in two transaction variant
Fix: Split the problem into left and right parts to avoid overlap

Summary

Find the best days to buy and sell stocks to maximize profit under different transaction limits.

Use when you want to maximize stock trading profit with constraints on number of transactions.

Track minimum prices and profits from left and right sides to combine results efficiently.

Practice

1. What is the main goal when solving the Buy and Sell Stocks problem with only one transaction allowed?

easy

A. Sell before buying to maximize profit

B. Minimize the buying price regardless of selling price

C. Buy and sell on the same day to avoid loss

D. Maximize the difference between a later selling price and an earlier buying price

Solution

1. Step 1: Understand the problem constraints

   The problem allows only one buy and one sell, so the goal is to find the maximum profit from one pair of days where buying day is before selling day.

2. Step 2: Identify the profit calculation

   Profit = selling price - buying price. We want to maximize this difference with the buying day before selling day.

3. Final Answer:

   Maximize the difference between a later selling price and an earlier buying price -> Option D

4. Quick Check:

   Profit = sell price - buy price [OK]

Hint: Find max difference with buy day before sell day [OK]

Common Mistakes:

• Ignoring the order of buy and sell days
• Trying to minimize price without considering selling
• Assuming multiple transactions allowed

2. Which of the following C++ code snippets correctly initializes a vector of stock prices for the Buy and Sell Stocks problem?

easy

A. std::vector prices = (7, 1, 5, 3, 6, 4);

B. std::vector<int> prices = {7, 1, 5, 3, 6, 4};

C. vector prices = [7, 1, 5, 3, 6, 4];

D. std::vector<int> prices = (7, 1, 5, 3, 6, 4);

Solution

1. Step 1: Recall correct vector initialization syntax

   In C++, a vector of integers is initialized with curly braces and type specified: std::vector<int> prices = {values};

2. Step 2: Check each option

   std::vector<int> prices = {7, 1, 5, 3, 6, 4}; uses correct syntax with std::vector<int> and curly braces. Options A, B, and D use incorrect syntax for vector initialization.

3. Final Answer:

   std::vector<int> prices = {7, 1, 5, 3, 6, 4}; -> Option B

4. Quick Check:

   Use std::vector<int> and braces {} [OK]

Hint: Use std::vector<int> and curly braces {} to initialize [OK]

Common Mistakes:

• Using square brackets [] instead of curly braces {}
• Omitting the type <int>
• Using parentheses () instead of braces

3. What is the output of the following C++ code that finds the maximum profit with unlimited transactions allowed?

std::vector<int> prices = {7, 1, 5, 3, 6, 4};
int maxProfit = 0;
for (int i = 1; i < prices.size(); i++) {
    if (prices[i] > prices[i - 1]) {
        maxProfit += prices[i] - prices[i - 1];
    }
}
std::cout << maxProfit << std::endl;

medium

A. 7

B. 5

C. 8

D. 6

Solution

1. Step 1: Understand the loop and profit calculation

   The code adds profit for every day where price increases from previous day, summing all positive differences.

2. Step 2: Calculate profits day by day

   Day 1 to 2: 1 - 7 = -6 (no profit)
   Day 2 to 3: 5 - 1 = 4 (add 4)
   Day 3 to 4: 3 - 5 = -2 (no profit)
   Day 4 to 5: 6 - 3 = 3 (add 3)
   Day 5 to 6: 4 - 6 = -2 (no profit)
   Total profit = 4 + 3 = 7

3. Final Answer:

   7 -> Option A

4. Quick Check:

   Sum of positive differences = 7 [OK]

Hint: Sum all positive price differences for unlimited transactions [OK]

Common Mistakes:

• Adding negative differences as profit
• Only considering one transaction
• Miscounting indices in loop

4. Identify the bug in this C++ code snippet that tries to find the maximum profit with only one transaction allowed:

std::vector<int> prices = {7, 1, 5, 3, 6, 4};
int minPrice = INT_MAX;
int maxProfit = 0;
for (int i = 0; i < prices.size(); i++) {
    if (prices[i] < minPrice) {
        minPrice = prices[i];
    } else if (prices[i] - minPrice > maxProfit) {
        maxProfit = prices[i] - minPrice;
    }
}
std::cout << maxProfit << std::endl;

medium

A. No bug, code works correctly

B. minPrice should be initialized to 0

C. maxProfit should be initialized to INT_MIN

D. Loop should start from i = 1 instead of 0

Solution

1. Step 1: Analyze initialization and loop

   minPrice is set to INT_MAX to find minimum price correctly. maxProfit starts at 0. Loop from 0 to end checks each price.

2. Step 2: Check logic correctness

   For each price, update minPrice if current price is lower. Else, calculate profit and update maxProfit if higher. This correctly finds max profit with one transaction.

3. Final Answer:

   No bug, code works correctly -> Option A

4. Quick Check:

   Correct minPrice and maxProfit updates [OK]

Hint: Initialize minPrice to INT_MAX and loop from 0 [OK]

Common Mistakes:

• Starting loop from 1 and missing first price
• Initializing minPrice to 0 causing wrong min
• Initializing maxProfit to INT_MIN causing negative profits

5. Given the prices {3, 3, 5, 0, 0, 3, 1, 4}, what is the maximum profit achievable with at most two transactions?

hard

A. 5

B. 7

C. 6

D. 8

Solution

1. Step 1: Understand two transactions limit

   We can buy and sell at most twice. We must find two pairs of buy-sell days maximizing total profit without overlap.

2. Step 2: Calculate max profit with two transactions

   First transaction: Buy at 3 (day 1), sell at 5 (day 3) profit = 2
   Second transaction: Buy at 0 (day 4), sell at 4 (day 8) profit = 4
   Total profit = 2 + 4 = 6

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Sum of two best transactions = 6 [OK]

Hint: Split prices into two parts, sum max profits [OK]

Common Mistakes:

• Counting overlapping transactions
• Only considering one transaction
• Misidentifying buy/sell days