Buy and Sell Stocks All Variants in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal in the 'Buy and Sell Stocks' problem?

To maximize profit by choosing the best days to buy and sell stocks given their prices over time.

beginner

What does the 'Buy and Sell Stocks with only one transaction' variant mean?

You can buy once and sell once. The goal is to find the maximum profit from a single buy-sell pair.

intermediate

How does the 'Buy and Sell Stocks with unlimited transactions' variant differ?

You can buy and sell multiple times, but you must sell before you buy again. The goal is to maximize total profit from many transactions.

intermediate

What is the key idea behind the 'Buy and Sell Stocks with cooldown' variant?

After selling a stock, you must wait one day before buying again. This adds a cooldown period that affects when you can trade.

intermediate

In the 'Buy and Sell Stocks with transaction fee' variant, how does the fee affect profit calculation?

Each sell transaction reduces profit by the fee amount, so you must consider fees when deciding to sell to maximize net profit.

In the single transaction variant, what is the best strategy to find max profit?

A Track the minimum price so far and calculate max profit by selling at current price

B Buy and sell on the first and last day

C Buy every day and sell every day

D Ignore prices and pick random days

Tracking the minimum price so far allows you to find the best day to buy and sell later for max profit.

In unlimited transactions, when should you buy and sell to maximize profit?

A Buy once and sell once only

B Sell before buying

C Buy and hold without selling

D Buy low and sell high every time price increases the next day

You profit from every increase by buying before the rise and selling after.

What does the cooldown period prevent in the cooldown variant?

A Buying multiple stocks at once

B Selling multiple times in a row

C Buying immediately after selling

D Selling on the first day

Cooldown means you must wait one day after selling before buying again.

How does a transaction fee affect the decision to sell?

A You sell only if profit after fee is positive

B You ignore the fee and sell anytime

C You never sell

D You pay fee when buying

Selling only makes sense if the profit after subtracting the fee is positive.

Which data structure or technique is commonly used to solve these stock problems efficiently?

A Graph Traversal

B Dynamic Programming

C Stack

D Binary Search Tree

Dynamic Programming helps track states like holding or not holding stock with constraints.

Explain how to solve the 'Buy and Sell Stocks with cooldown' variant step-by-step.

Think about what happens after selling and how cooldown affects buying.

Describe the difference between the single transaction and unlimited transactions variants and how it changes the approach.

Focus on how many times you can trade and how profit is calculated.

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