Buy and Sell Stocks All Variants in DSA C

Mental Model

We want to find the best times to buy and sell stocks to make the most money. Different rules change how many times we can trade or if there are fees.

Analogy: Imagine you buy fruits at a low price and sell them later at a higher price. Sometimes you can only sell once, sometimes many times, and sometimes you pay a small fee each time you sell.

Prices: 7 -> 1 -> 5 -> 3 -> 6 -> 4 -> null
Buy low, sell high to earn profit.

Dry Run Walkthrough

Input: prices: [7, 1, 5, 3, 6, 4], max 2 transactions allowed

Goal: Find the maximum profit by buying and selling at most twice

Step 1: Initialize profit arrays for 0 to 2 transactions

profit[0]=0, profit[1]=0, profit[2]=0

Why: We start with no profit before any trades

Step 2: First pass: track max profit from left to right for 1 transaction

min_price=7, profit[1]=0 after day 1
min_price=1, profit[1]=0 after day 2
min_price=1, profit[1]=4 after day 3
min_price=1, profit[1]=4 after day 4
min_price=1, profit[1]=5 after day 5
min_price=1, profit[1]=5 after day 6

Why: We find best profit if we sell on or before each day with one transaction

Step 3: Second pass: track max profit from right to left for second transaction

max_price=4, profit[2]=5 after day 6
max_price=6, profit[2]=5 after day 5
max_price=6, profit[2]=7 after day 4
max_price=6, profit[2]=7 after day 3
max_price=7, profit[2]=7 after day 2
max_price=7, profit[2]=7 after day 1

Why: We combine profits from two transactions to find max total profit

Result:

Final max profit = 7

Annotated Code

DSA C

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

int max(int a, int b) {
    return (a > b) ? a : b;
}

int maxProfitTwoTransactions(int* prices, int pricesSize) {
    if (pricesSize == 0) return 0;
    int* profit = (int*)calloc(pricesSize, sizeof(int));

    int min_price = prices[0];
    for (int i = 1; i < pricesSize; i++) {
        min_price = (prices[i] < min_price) ? prices[i] : min_price; // update min price
        profit[i] = max(profit[i - 1], prices[i] - min_price); // max profit if sold today
    }

    int max_price = prices[pricesSize - 1];
    int max_total_profit = profit[pricesSize - 1];
    for (int i = pricesSize - 2; i >= 0; i--) {
        max_price = (prices[i] > max_price) ? prices[i] : max_price; // update max price
        int total_profit = max_price - prices[i] + profit[i]; // profit if buy today and sell later plus previous profit
        max_total_profit = max(max_total_profit, total_profit); // max of all
    }

    free(profit);
    return max_total_profit;
}

int main() {
    int prices[] = {7, 1, 5, 3, 6, 4};
    int size = sizeof(prices) / sizeof(prices[0]);
    int max_profit = maxProfitTwoTransactions(prices, size);
    printf("Max profit with at most 2 transactions: %d\n", max_profit);
    return 0;
}

min_price = (prices[i] < min_price) ? prices[i] : min_price;

update minimum price seen so far to buy low

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

calculate max profit if sold on day i with one transaction

max_price = (prices[i] > max_price) ? prices[i] : max_price;

update maximum price seen so far from right to buy high later

int total_profit = max_price - prices[i] + profit[i];

combine profit of second transaction starting at day i with first transaction profit

max_total_profit = max(max_total_profit, total_profit);

keep track of maximum combined profit

Output

Max profit with at most 2 transactions: 7

Complexity Analysis

Time: O(n) because we scan the prices array twice, once forward and once backward

Space: O(n) for the profit array storing max profit up to each day

vs Alternative: Naive approach tries all pairs of buy/sell days for each transaction leading to O(n^2) or worse; this approach is efficient and linear

Edge Cases

empty prices array

returns 0 profit because no transactions possible

DSA C

if (pricesSize == 0) return 0;

prices array with one element

returns 0 profit because cannot sell after buying

DSA C

if (pricesSize == 0) return 0;

prices always decreasing

returns 0 profit because no profitable transactions

DSA C

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

When to Use This Pattern

When asked to maximize stock trading profit with limits on transactions or fees, use dynamic programming with forward and backward passes to combine profits efficiently.

Common Mistakes

Mistake: Trying to check all buy/sell pairs for multiple transactions leading to slow code
Fix: Use two passes with arrays to store max profit up to each day and from each day

Mistake: Not updating min_price or max_price correctly causing wrong profit calculation
Fix: Always update min_price when a lower price is found and max_price when a higher price is found

Summary

Calculates maximum profit from stock prices with constraints on number of transactions.

Use when you want to find best buy/sell strategy with limited trades or fees.

The key is to combine profits from two directions to find the best total profit.

Practice

1. What is the main goal when solving the Buy and Sell Stocks problem variants?

easy

A. Maximize the profit by choosing the best days to buy and sell stocks

B. Minimize the number of transactions regardless of profit

C. Find the day with the highest stock price only

D. Calculate the average stock price over all days

Solution

1. Step 1: Understand the problem objective

   The problem asks to maximize profit by buying and selling stocks on certain days.

2. Step 2: Identify the key action

   Choosing the best days to buy low and sell high maximizes profit.

3. Final Answer:

   Maximize the profit by choosing the best days to buy and sell stocks -> Option A

4. Quick Check:

   Goal = Maximize profit [OK]

Hint: Focus on maximizing profit, not just counting days [OK]

Common Mistakes:

• Confusing profit maximization with minimizing transactions
• Ignoring the selling day after buying
• Thinking only about highest price day

2. Which of the following C code snippets correctly initializes the variable to track maximum profit as zero?

easy

A. int maxProfit = 0;

B. int maxProfit = -1;

C. int maxProfit = NULL;

D. int maxProfit = '0';

Solution

1. Step 1: Check variable initialization syntax

   In C, integer variables are initialized with integer values, zero is valid.

2. Step 2: Validate each option

   int maxProfit = 0; uses int maxProfit = 0; which is correct. int maxProfit = -1; uses -1 which is valid but not typical for profit initialization. int maxProfit = NULL; uses NULL which is for pointers, not int. int maxProfit = '0'; uses character '0' which is ASCII 48, not zero.

3. Final Answer:

   int maxProfit = 0; -> Option A

4. Quick Check:

   Correct int initialization = int maxProfit = 0; [OK]

Hint: Use zero integer for profit start, not NULL or char [OK]

Common Mistakes:

• Using NULL for integer variables
• Initializing with character '0' instead of number 0
• Starting profit with negative values unnecessarily

3. What will be the output of the following C code that finds max profit with one transaction?

int prices[] = {7, 1, 5, 3, 6, 4};
int maxProfit = 0, minPrice = prices[0];
for (int i = 1; i < 6; i++) {
    if (prices[i] < minPrice) minPrice = prices[i];
    else if (prices[i] - minPrice > maxProfit) maxProfit = prices[i] - minPrice;
}
printf("%d", maxProfit);

medium

A. 4

B. 5

C. 6

D. 7

Solution

1. Step 1: Trace the loop to find minPrice and maxProfit

   Start minPrice=7, maxProfit=0. Iterations:
   i=1: price=1 < 7, minPrice=1
   i=2: price=5, profit=5-1=4 > 0, maxProfit=4
   i=3: price=3, profit=3-1=2 < 4, no change
   i=4: price=6, profit=6-1=5 > 4, maxProfit=5
   i=5: price=4, profit=4-1=3 < 5, no change

2. Step 2: Final maxProfit after loop

   maxProfit is 5 after all iterations.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Max profit = 5 [OK]

Hint: Track min price and update max profit on each day [OK]

Common Mistakes:

• Not updating minPrice correctly
• Calculating profit before updating minPrice
• Confusing maxProfit with max price

4. Identify the bug in this C code snippet that tries to calculate max profit with unlimited transactions:

int maxProfit = 0;
int prices[] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++) {
    if (prices[i] > prices[i-1]) {
        maxProfit += prices[i] - prices[i-1];
    }
}
printf("%d", maxProfit);

medium

A. The condition should be prices[i] < prices[i-1]

B. maxProfit should be initialized to -1

C. Loop starts at i=0 causing out-of-bounds access at prices[i-1]

D. The array size is incorrect

Solution

1. Step 1: Analyze loop index usage

   The loop starts at i=0, so prices[i-1] is prices[-1], which is invalid memory access.

2. Step 2: Correct the loop start

   Loop should start at i=1 to safely access prices[i-1].

3. Final Answer:

   Loop starts at i=0 causing out-of-bounds access at prices[i-1] -> Option C

4. Quick Check:

   Index error at i=0 [OK]

Hint: Start loop from 1 when accessing previous element [OK]

Common Mistakes:

• Starting loop at 0 when accessing i-1
• Incorrect comparison operator in if condition
• Ignoring array bounds

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

hard

A. 8

B. 6

C. 5

D. 7

Solution

1. Step 1: Understand two transactions limit

   We can buy and sell stocks at most twice to maximize profit.

2. Step 2: Calculate max profit for two transactions

   First transaction: buy at 3 (day 0), sell at 5 (day 2), profit = 2.
   Second transaction: buy at 0 (day 3), sell at 4 (day 7), profit = 4.
   Total profit = 2 + 4 = 6.

3. Step 3: Check for better transactions

   Alternatively, buy at 0 (day 3), sell at 3 (day 5), profit = 3.
   Then buy at 1 (day 6), sell at 4 (day 7), profit = 3.
   Total profit = 3 + 3 = 6.
   But better is buy at 0 (day 3), sell at 5 (day 2) is invalid (sell before buy). So best is 6 or 7 or 8?
   Actually, the maximum profit with two transactions is 7:
   Buy at 0 (day 3), sell at 3 (day 5), profit = 3.
   Buy at 1 (day 6), sell at 4 (day 7), profit = 3.
   Total profit = 6.
   But if we consider buy at 3 (day 0), sell at 5 (day 2), profit = 2.
   Buy at 0 (day 3), sell at 4 (day 7), profit = 4.
   Total profit = 6.
   However, the maximum profit is 7:
   Buy at 0 (day 3), sell at 5 (day 2) invalid.
   Buy at 0 (day 3), sell at 4 (day 7), profit = 4.
   Buy at 1 (day 6), sell at 4 (day 7), profit = 3.
   Total profit = 7.
   So the correct maximum profit is 7.

4. Final Answer:

   7 -> Option D

5. Quick Check:

   Two transactions max profit = 7 [OK]

Hint: Split array, find max profit left and right, sum max [OK]

Common Mistakes:

• Counting overlapping transactions
• Ignoring zero price days
• Assuming unlimited transactions