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 usually give you a list of stock prices over days and ask for the maximum profit you can make under certain rules. Variants include limits on the number of transactions, cooldown periods, or transaction fees. Understanding these helps solve many real-world financial decision problems and algorithmic challenges.

Why it matters

Without these concepts, you might miss how to optimize profits or minimize losses in trading scenarios. They teach how to handle constraints and make decisions over time, which applies beyond stocks to resource allocation and scheduling. Without this knowledge, solutions would be inefficient or incorrect, leading to lost opportunities or wasted resources.

Where it fits

Before this, you should understand arrays, basic loops, and simple greedy or dynamic programming ideas. After mastering this, you can explore more complex dynamic programming problems, financial modeling algorithms, and optimization techniques.

Mental Model

Core Idea

Maximize profit by choosing the best buy and sell days under given constraints using patterns of tracking minimum costs and maximum gains.

Think of it like...

Imagine buying fruits at a market where prices change daily. You want to buy low and sell high, but sometimes you can only buy and sell a limited number of times or must wait a day before buying again. Planning your buys and sells carefully is like solving these stock problems.

Prices:  [7, 1, 5, 3, 6, 4]
Buy on day 2 (price=1) → Sell on day 5 (price=6)
Profit = 6 - 1 = 5

┌─────────────┐
│ Day: 1 2 3 4 5 6 │
│ Price:7 1 5 3 6 4 │
└─────────────┘

Track min price and max profit as you move through days.

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, track the lowest price seen so far and calculate potential profit by selling on the current day. Update max profit if this potential profit is higher. Example: Prices = [7,1,5,3,6,4] - Lowest price starts at 7 - Day 2 price=1, update lowest price to 1 - Day 3 price=5, profit=5-1=4, max profit=4 - Day 5 price=6, profit=6-1=5, max profit=5 Return max profit = 5.

Result

Maximum profit is 5 by buying at price 1 and selling at price 6.

Understanding that tracking the minimum price so far lets you calculate the best profit in one pass is key to efficient solutions.

2

Foundation

Unlimited Transactions Maximum Profit

Concept: Calculate maximum profit when you can buy and sell multiple times without limits.

You can buy and sell as many times as you want, but you must sell before buying again. The strategy is to sum all positive price differences between consecutive days. Example: Prices = [7,1,5,3,6,4] - Profit = (5-1) + (6-3) = 4 + 3 = 7 This adds all upward movements.

Result

Maximum profit is 7 by multiple buy-sell pairs.

Knowing that summing all positive gains captures all profitable trades simplifies the problem drastically.

3

Intermediate

At Most Two Transactions

🤔Before reading on: do you think summing two best single transactions always gives the max profit? Commit to yes or no.

Concept: Limit the number of transactions to two and find the maximum profit achievable.

Use two passes: - Forward pass: for each day, track max profit if sold on or before that day. - Backward pass: for each day, track max profit if bought on or after that day. Combine these to find max sum of two transactions. Example: Prices = [3,3,5,0,0,3,1,4] - Forward max profits: [0,0,2,2,2,3,3,4] - Backward max profits: [4,4,4,4,4,3,3,0] - Max combined profit = 6.

Result

Maximum profit is 6 with two transactions.

Splitting the problem into two parts and combining results allows handling transaction limits efficiently.

4

Intermediate

K Transactions Using Dynamic Programming

🤔Before reading on: do you think a greedy approach works for any number of transactions? Commit to yes or no.

Concept: Use dynamic programming to handle any number of transactions with time complexity O(k*n).

Define dp arrays: - dp[t][d]: max profit using at most t transactions until day d. Transition: - For each transaction t and day d, dp[t][d] = max(dp[t][d-1], prices[d] + maxDiff) - maxDiff = max(maxDiff, dp[t-1][d-1] - prices[d]) This tracks best profit by either skipping or selling on day d.

Result

Maximum profit computed for k transactions efficiently.

Dynamic programming breaks down complex constraints into manageable subproblems.

5

Intermediate

Cooldown Period Between Transactions

🤔Before reading on: do you think you can buy immediately after selling without cooldown? Commit to yes or no.

Concept: Add a cooldown day after selling before buying again, changing the state transitions.

Use three states: - hold: max profit holding a stock - sold: max profit just sold stock - rest: max profit doing nothing Transitions: - hold = max(hold, rest - price) - sold = hold + price - rest = max(rest, prev_sold) Cooldown forces waiting one day after selling.

Result

Maximum profit with cooldown constraint.

Modeling states explicitly captures cooldown constraints cleanly.

6

Advanced

Transaction Fee Impact on Profit

🤔Before reading on: does adding a fee always reduce profit by fee amount? Commit to yes or no.

Concept: Incorporate a fixed fee per transaction, affecting buy/sell decisions.

Modify hold state to subtract fee when selling: - hold = max(hold, rest - price) - sold = hold + price - fee - rest = max(rest, sold) Fee discourages small profit trades.

Result

Maximum profit accounting for transaction fees.

Fees change the threshold for profitable trades, requiring careful state updates.

7

Expert

Optimizing Space and Time for Large K

🤔Before reading on: do you think DP with O(k*n) is always efficient for large k? Commit to yes or no.

Concept: When k is large (≥ n/2), treat as unlimited transactions to optimize performance.

If k >= n/2, use the unlimited transactions approach summing positive differences. Else, use DP. This avoids expensive DP when transactions are effectively unlimited.

Result

Efficient solution for all k values.

Recognizing problem constraints lets you switch to simpler algorithms, improving efficiency.

Under the Hood

These problems use dynamic programming to track states representing holding or not holding stocks, number of transactions done, and cooldown or fees. The algorithm updates these states day by day, using previous results to build up the solution. Internally, arrays or variables store intermediate profits, and transitions represent buy, sell, or rest actions under constraints.

Why designed this way?

Stock trading problems model real-world constraints like limited trades, cooldowns, and fees. Dynamic programming was chosen because it efficiently explores all possible decisions over time without redundant calculations. Alternatives like brute force are too slow, and greedy fails under constraints, so DP balances correctness and performance.

┌───────────────┐
│ Day 0 States  │
│ hold= -price  │
│ sold= 0       │
│ rest= 0       │
└─────┬─────────┘
      │
      ▼
┌───────────────┐
│ Day 1 States  │
│ hold= max(prev_hold, prev_rest - price)
│ sold= prev_hold + price - fee
│ rest= max(prev_rest, prev_sold)
└─────┬─────────┘
      │
     ...
      │
      ▼
┌───────────────┐
│ Final Result  │
│ max(sold, rest)│
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does summing all positive price differences always give the max profit with transaction limits? Commit yes or no.

Common Belief: Summing all positive gains always gives the maximum profit regardless of transaction limits.

Reality: When transactions are limited, summing all positive differences can exceed allowed transactions and is invalid.

Why it matters: Using this approach with limits leads to incorrect profits and wrong solutions.

Quick: Can you buy and sell on the same day for profit? Commit yes or no.

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

Reality: You must buy before you sell, so buying and selling on the same day is not allowed.

Why it matters: Ignoring this leads to invalid trades and incorrect profit calculations.

Quick: Does adding a transaction fee always reduce profit by that fee amount? Commit yes or no.

Common Belief: Transaction fees simply subtract from total profit by a fixed amount.

Reality: Fees affect each transaction decision, sometimes making small trades unprofitable and changing when to buy or sell.

Why it matters: Misunderstanding fees causes suboptimal trading strategies and lower profits.

Quick: Is dynamic programming always necessary for any number of transactions? Commit yes or no.

Common Belief: DP is always required regardless of transaction count.

Reality: When transactions are unlimited or very large, a simple greedy approach suffices and is more efficient.

Why it matters: Using DP unnecessarily wastes time and resources.

Expert Zone

1

Tracking states with minimal variables instead of full arrays can reduce memory usage significantly.

2

Recognizing when transaction limits exceed half the number of days allows switching to simpler algorithms.

3

Cooldown and fee constraints can be combined in state machines but require careful state design to avoid bugs.

When NOT to use

Avoid DP for very large k values where k >= n/2; use unlimited transactions approach instead. Also, if real-time or streaming data is involved, these batch DP methods may not apply; consider online algorithms.

Production Patterns

Used in financial software for portfolio optimization, algorithmic trading bots, and risk management tools. Also appears in coding interviews to test dynamic programming and state management skills.

Connections

Dynamic Programming

Builds-on

Understanding stock problems deepens grasp of DP state transitions and optimization under constraints.

Resource Allocation in Operations Research

Similar pattern

Stock trading constraints mirror resource limits and scheduling in operations research, showing cross-domain optimization.

Behavioral Economics

Application domain

Modeling cooldowns and fees reflects real human trading behaviors and market frictions studied in behavioral economics.

Common Pitfalls

#1 Ignoring transaction limits and summing all positive gains.

Wrong approach:

int maxProfit = 0;
for (int i = 1; i < prices.Length; i++) {
if (prices[i] > prices[i - 1])
maxProfit += prices[i] - prices[i - 1];
}
return maxProfit; // Incorrect if transactions limited

Correct approach:

Use DP to track max profit with transaction limits as in the k transactions step.

Root cause:

Misunderstanding that unlimited transactions logic applies to limited transactions.

#2 Buying and selling on the same day.

Wrong approach:

if (prices[i] > prices[i]) {
profit += prices[i] - prices[i];
}
// This is logically invalid

Correct approach:

Ensure buy day < sell day and track minimum price before current day.

Root cause:

Confusing problem constraints and ignoring order of operations.

#3 Not accounting for cooldown days properly.

Wrong approach:

hold = Math.Max(hold, rest - price);
sold = hold + price;
rest = Math.Max(rest, sold);
// Missing cooldown logic

Correct approach:

Implement rest state to enforce cooldown:
rest = Math.Max(rest, prevSold);
hold = Math.Max(hold, rest - price);
sold = hold + price;

Root cause:

Overlooking state dependencies and cooldown constraints.

Key Takeaways

Maximizing stock trading profit involves carefully tracking buy and sell decisions over time under constraints.

Simple one-pass solutions work for single or unlimited transactions, but dynamic programming is needed for limits and cooldowns.

Modeling problem states explicitly helps handle complex rules like cooldowns and fees.

Recognizing problem constraints can simplify solutions and improve efficiency.

These problems teach valuable lessons in optimization, state management, and real-world decision making.

Practice

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

easy

A. Minimize the number of transactions regardless of profit

B. Find the stock price on the last day only

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

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 C

4. Quick Check:

   Goal = Maximize profit [OK]

Hint: Focus on profit maximization, not just transactions [OK]

Common Mistakes:

• Confusing profit with number of transactions
• Ignoring the buy before sell rule
• Trying to find average price instead of max profit

2. Which of the following C# code snippets correctly initializes an array of stock prices for the Buy and Sell Stocks problem?

easy

A. int prices[] = new int[6] {7, 1, 5, 3, 6, 4};

B. int prices = {7, 1, 5, 3, 6, 4};

C. int[] prices = (7, 1, 5, 3, 6, 4);

D. int[] prices = new int[] {7, 1, 5, 3, 6, 4};

Solution

1. Step 1: Check correct array initialization syntax in C#

   In C#, arrays are initialized with int[] prices = new int[] { ... };.

2. Step 2: Verify each option

   int[] prices = new int[] {7, 1, 5, 3, 6, 4}; uses correct syntax. The other options have invalid syntax: one declares a single int without array type, another uses parentheses instead of braces, and the last has incorrect array declaration style.

3. Final Answer:

   int[] prices = new int[] {7, 1, 5, 3, 6, 4}; -> Option D

4. Quick Check:

   Correct C# array syntax = int[] prices = new int[] {7, 1, 5, 3, 6, 4}; [OK]

Hint: Use int[] arr = new int[] { ... }; for arrays [OK]

Common Mistakes:

• Omitting 'new int[]' when initializing arrays
• Using parentheses instead of braces
• Declaring arrays like in C or Java incorrectly

3. What is the output of the following C# code that finds the maximum profit with only one transaction allowed?

int[] prices = {7, 1, 5, 3, 6, 4};
int minPrice = int.MaxValue;
int maxProfit = 0;
foreach (int price in prices) {
    if (price < minPrice) minPrice = price;
    else if (price - minPrice > maxProfit) maxProfit = price - minPrice;
}
Console.WriteLine(maxProfit);

medium

A. 6

B. 5

C. 4

D. 7

Solution

1. Step 1: Trace the minimum price and max profit updates

   Prices: 7,1,5,3,6,4. Min price updates to 7 then 1. Max profit updates when price - minPrice > maxProfit: 5-1=4, 6-1=5.

2. Step 2: Identify final max profit

   Max profit is 5, achieved by buying at 1 and selling at 6.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Max profit one transaction = 5 [OK]

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

Common Mistakes:

• Confusing max profit with max price
• Not updating min price correctly
• Calculating profit without checking min price

4. The following code is intended to calculate the maximum profit with unlimited transactions allowed. What is the bug?

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

medium

A. There is no bug; code works correctly

B. The code does not handle empty price array

C. The loop should start from i = 0

D. The code incorrectly adds profit when prices decrease

Solution

1. Step 1: Understand the logic for unlimited transactions

   The code adds profit for every increase from day i-1 to i, which is correct for unlimited transactions.

2. Step 2: Check for bugs

   The loop starts at 1 to compare with previous day. It skips empty array handling but not asked here. No incorrect profit addition.

3. Final Answer:

   There is no bug; code works correctly -> Option A

4. Quick Check:

   Unlimited transactions profit logic = correct [OK]

Hint: Add profit only when price increases day-to-day [OK]

Common Mistakes:

• Starting loop at wrong index
• Adding profit on price drops
• Ignoring empty or single-element arrays

5. Given the prices array {3, 3, 5, 0, 0, 3, 1, 4} and a limit of at most two transactions, what is the maximum profit achievable?

hard

A. 8

B. 7

C. 5

D. 6

Solution

1. Step 1: Understand the two transactions limit

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

2. Step 2: Calculate max profit by splitting days

   First transaction: buy at 3, sell at 5 (profit 2). Second transaction: buy at 0, sell at 4 (profit 4). Total profit = 2 + 4 = 6. But better transactions are buy at 0 sell at 3 (profit 3), then buy at 1 sell at 4 (profit 3), total 6. However, the maximum profit is actually 8 by buying at 0 and selling at 5 (profit 5), then buying at 1 and selling at 4 (profit 3).

3. Final Answer:

   8 -> Option A

4. Quick Check:

   Two transactions max profit = 8 [OK]

Hint: Split array to find best two transaction profits [OK]

Common Mistakes:

• Counting more than two transactions
• Not choosing optimal buy/sell days
• Adding profits incorrectly