Buy and Sell Stocks All Variants in DSA C++ - Deep Dive

Overview - Buy and Sell Stocks All Variants

What is it?

Buying and selling stocks problems involve deciding the best times to buy and sell stocks to maximize profit. These problems vary by constraints like how many transactions you can make, cooldown periods, or transaction fees. The goal is to find the maximum profit possible given these rules. They help us understand how to optimize decisions over time with changing prices.

Why it matters

Without these strategies, investors might lose money by buying or selling at the wrong times. These problems teach us how to make smart choices in uncertain and changing environments, which applies beyond stocks to many real-life decisions. They also help build skills in dynamic programming and optimization, which are key in software and data science.

Where it fits

Before this, learners should understand arrays, basic loops, and simple greedy algorithms. After mastering these variants, learners can explore advanced dynamic programming, sliding window techniques, and real-time decision-making algorithms.

Mental Model

Core Idea

Maximize profit by choosing the best buy and sell points under given constraints over a sequence of stock prices.

Think of it like...

Imagine you are at a fruit market where prices change daily. You want to buy fruit when cheap and sell when expensive, but sometimes you can only buy and sell a limited number of times or must wait a day after selling before buying again.

Prices:  7 ──┐       ┌── 5 ──┐       ┌── 3 ──┐
          │       │       │       │       │
Days:    0   1   2   3   4   5   6   7   8
Buy/Sell: B       S       B       S       B
Profit:  +0      +5      +0      +2      +0

Build-Up - 7 Steps

1

Foundation

Single Transaction Maximum Profit

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

Given an array of prices, we track the lowest price seen so far and calculate profit if we sell today. We update max profit if this profit is higher. This is a simple linear scan.

Result

For prices [7,1,5,3,6,4], max profit is 5 (buy at 1, sell at 4).

Understanding that tracking minimum price and potential profit in one pass solves the simplest stock problem efficiently.

2

Foundation

Multiple Transactions Unlimited

Concept: Allow unlimited buy and sell transactions to maximize total profit.

We add up all positive differences between consecutive days because buying before a rise and selling at the peak captures all profit opportunities.

Result

For prices [1,2,3,4,5], max profit is 4 (buy day 0, sell day 4).

Knowing that summing all upward price moves captures maximum profit when transactions are unlimited.

3

Intermediate

At Most Two Transactions

🤔Before reading on: do you think solving two transactions is just twice the single transaction solution? Commit to yes or no.

Concept: Maximize profit with at most two buy-sell pairs using dynamic programming.

We split the array into two parts for each day: max profit from start to that day and max profit from that day to end. The answer is max sum of these two profits. We compute prefix and suffix profits with single transaction logic.

Result

For prices [3,3,5,0,0,3,1,4], max profit is 6 (buy at 3 sell at 5, buy at 6 sell at 7).

Understanding how to combine two single-transaction profits efficiently to handle limited transactions.

4

Intermediate

K Transactions Generalization

🤔Before reading on: do you think the solution for k transactions is just repeating the two transactions method k times? Commit to yes or no.

Concept: Use dynamic programming with states representing number of transactions and days to find max profit for k transactions.

We maintain a DP table where dp[t][d] is max profit using at most t transactions until day d. We update dp using max of not trading or selling today after buying at some previous day. Optimized with tracking max difference to avoid nested loops.

Result

For prices [2,4,1], k=2, max profit is 2 (buy at 0 sell at 1).

Knowing how to extend the problem to any number of transactions using DP and optimization.

5

Intermediate

Cooldown Period After Selling

🤔Before reading on: do you think cooldown means you cannot buy or sell the next day? Commit to your answer.

Concept: Add a cooldown day after selling where buying is not allowed, changing state transitions.

We track three states per day: holding stock, not holding and in cooldown, and not holding and free to buy. Transitions update these states considering cooldown constraints.

Result

For prices [1,2,3,0,2], max profit is 3 (buy day 0 sell day 2 cooldown day 3 buy day 4 sell day 4).

Understanding how cooldown changes the problem to require state tracking beyond simple buy/sell.

6

Advanced

Transaction Fee Impact

🤔Before reading on: do you think transaction fee applies only once or both on buy and sell? Commit to your answer.

Concept: Incorporate a fixed fee cost per transaction reducing profit from each sell.

We track two states: holding and not holding. When selling, subtract fee from profit. Update states accordingly to maximize net profit.

Result

For prices [1,3,2,8,4,9], fee=2, max profit is 8.

Knowing how fees reduce profit and require adjusting state transitions to avoid unprofitable trades.

7

Expert

Optimized Space and Time DP

🤔Before reading on: do you think storing full DP tables is always necessary for these problems? Commit to yes or no.

Concept: Use rolling variables and mathematical insights to reduce DP space and time complexity.

Instead of full DP tables, keep track of key variables like max profit after certain transactions and holding states. This reduces memory and speeds up computation.

Result

For large inputs, solution runs in O(nk) time with O(k) space instead of O(nk) space.

Understanding how to optimize DP solutions for performance critical applications.

Under the Hood

These problems use dynamic programming to remember past decisions and their profits, avoiding repeated calculations. States represent whether you hold stock or not, how many transactions done, and cooldown or fees. Transitions update these states day by day based on price changes and constraints.

Why designed this way?

Stock trading is sequential and decisions depend on past actions. DP fits naturally to model this. Early greedy methods failed for complex constraints, so DP was designed to handle all cases efficiently.

Day 0    Day 1    Day 2    Day 3    Day 4
┌─────┐ ┌─────┐ ┌─────┐ ┌─────────┐ ┌─────┐
│Hold │→│Hold │→│Sell │→│Cooldown │→│Buy  │
└─────┘ └─────┘ └─────┘ └─────────┘ └─────┘
States track profit and transitions based on price and rules.

Myth Busters - 4 Common Misconceptions

Quick: Is buying and selling on the same day allowed for profit? Commit yes or no.

Common Belief: You can buy and sell on the same day to make profit.

Reality: You cannot buy and sell on the same day; you must buy before you sell on a later day.

Why it matters: Assuming same-day trades leads to incorrect profit calculations and invalid solutions.

Quick: Does unlimited transactions always mean infinite profit? Commit yes or no.

Common Belief: With unlimited transactions, you can make infinite profit if prices rise.

Reality: Profit is limited by actual price differences; you cannot sell more than you own or buy negative stocks.

Why it matters: Misunderstanding this causes unrealistic expectations and wrong algorithm designs.

Quick: Does cooldown prevent selling or buying the next day? Commit your answer.

Common Belief: Cooldown means you cannot sell the day after selling.

Reality: Cooldown means you cannot buy the day after selling, but you can sell if you already hold stock.

Why it matters: Confusing cooldown rules leads to wrong state transitions and incorrect profits.

Quick: Is transaction fee applied once per transaction or per share? Commit your answer.

Common Belief: Transaction fee applies per share bought or sold.

Reality: Transaction fee applies once per transaction (usually on sell), not per share.

Why it matters: Misapplying fees inflates costs and underestimates profit.

Expert Zone

1

Tracking states with cooldown or fees requires careful ordering of updates to avoid overwriting needed values.

2

Optimizing DP by maintaining max differences reduces nested loops and improves runtime significantly.

3

Edge cases like constant prices or strictly decreasing prices reveal subtle bugs in state transitions.

When NOT to use

These DP solutions are not suitable for real-time streaming data or when price predictions are uncertain. Instead, use heuristic or machine learning models for live trading decisions.

Production Patterns

In production, these algorithms are used for backtesting trading strategies, risk assessment, and automated trading bots with constraints like fees and cooldowns modeled explicitly.

Connections

Dynamic Programming

Builds-on

Understanding stock problems deepens grasp of DP state management and optimization techniques.

Operations Research

Shares optimization patterns

Stock trading problems mirror resource allocation and scheduling challenges studied in operations research.

Behavioral Economics

Applies decision-making under constraints

Learning these algorithms helps appreciate how humans make financial decisions with limits and costs.

Common Pitfalls

#1 Ignoring cooldown leads to overestimating profit.

Wrong approach:

int maxProfit(vector& prices) {
int profit = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] > prices[i-1]) profit += prices[i] - prices[i-1];
}
return profit;
}

Correct approach:

int maxProfit(vector& prices) {
int n = prices.size();
if (n <= 1) return 0;
vector hold(n, INT_MIN), sold(n, 0), rest(n, 0);
hold[0] = -prices[0];
for (int i = 1; i < n; i++) {
hold[i] = max(hold[i-1], rest[i-1] - prices[i]);
sold[i] = hold[i-1] + prices[i];
rest[i] = max(rest[i-1], sold[i-1]);
}
return max(sold[n-1], rest[n-1]);
}

Root cause:

Not modeling cooldown states causes invalid consecutive buys or sells.

#2 Applying transaction fee on both buy and sell doubles cost.

Wrong approach:

buy = max(buy, sell - prices[i] - fee); // fee subtracted on buy

Correct approach:

buy = max(buy, sell - prices[i]); // fee subtracted only on sell
sell = max(sell, buy + prices[i] - fee);

Root cause:

Misunderstanding when fees apply leads to incorrect profit calculations.

#3 Using nested loops without optimization causes timeouts for large k.

Wrong approach:

for (int t = 1; t <= k; t++) {
for (int d = 1; d < n; d++) {
for (int m = 0; m < d; m++) {
dp[t][d] = max(dp[t][d], dp[t-1][m] + prices[d] - prices[m]);
}
}
}

Correct approach:

for (int t = 1; t <= k; t++) {
int maxDiff = -prices[0];
for (int d = 1; d < n; d++) {
dp[t][d] = max(dp[t][d-1], prices[d] + maxDiff);
maxDiff = max(maxDiff, dp[t-1][d] - prices[d]);
}
}

Root cause:

Not using maxDiff optimization leads to O(n^2 k) instead of O(n k) time.

Key Takeaways

Stock buy and sell problems teach how to optimize sequential decisions under constraints.

Dynamic programming with state tracking is essential for handling cooldowns, fees, and transaction limits.

Simple greedy methods work only for unlimited transactions without constraints.

Optimizing DP with rolling variables and max differences improves performance for large inputs.

Understanding problem constraints deeply prevents common mistakes and incorrect profit calculations.

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