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 ask how to maximize profit by choosing the best days to buy and sell stocks. These problems vary by constraints like how many transactions you can make or if you have to wait between transactions. They help us understand how to make smart decisions over time with changing prices. This topic covers all common versions of these problems.

Why it matters

Without these strategies, investors might lose money by buying or selling at the wrong time. These problems teach how to spot patterns and plan actions to get the most profit. Beyond stocks, they show how to solve problems where you must make the best choices step-by-step under limits. Without this, many real-world decisions would be guesswork.

Where it fits

Before this, you should know arrays and basic loops. After this, you can learn dynamic programming deeply and other optimization problems like knapsack or scheduling. This topic builds your skill in planning with constraints and helps with many real-world decision-making algorithms.

Mental Model

Core Idea

Maximize profit by choosing the best buy and sell days under given rules and limits.

Think of it like...

It's like buying fruits at a market when prices are low and selling them later when prices rise, but sometimes you can only carry a few fruits or must wait before buying again.

Prices:  [7]─[1]─[5]─[3]─[6]─[4]
Buy:       ↑         ↑        ↑
Sell:          ↑         ↑        ↑
Goal: Maximize sum of (sell - buy) pairs under rules

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, find the maximum difference between a later sell price and an earlier buy price. We scan prices, track the lowest price so far, and calculate profit if sold today. Keep the max profit found.

Result

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

Understanding how to track minimum price and calculate profit in one pass is the base for all variants.

2

Foundation

Unlimited Transactions Profit

Concept: Calculate max 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 trick is to sum all positive price differences between consecutive days.

Result

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

Knowing that summing all upward moves captures max profit without complex tracking simplifies the problem.

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: Find max profit with at most two buy-sell pairs.

We split the array into two parts at each day. Calculate max profit from start to that day and from that day to end. The answer is max sum of these two profits. This requires two passes and storing intermediate results.

Result

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

Understanding how to combine two single-transaction profits efficiently is key to solving limited transactions.

4

Intermediate

K Transactions with Dynamic Programming

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

Concept: Use dynamic programming to handle any number k of transactions with state tracking.

We use DP arrays to track max profit at each transaction count and day, considering buy or sell actions. The complexity is O(k*n). This generalizes previous cases.

Result

For k=2 and prices [3,2,6,5,0,3], max profit is 7.

Knowing how to model transactions as states and transitions unlocks solving complex constraints.

5

Intermediate

Cooldown Period Between Transactions

🤔Before reading on: do you think cooldown means you cannot buy the next day after selling? Commit to yes or no.

Concept: Add a cooldown day after selling before buying again.

We track three states: holding stock, not holding and in cooldown, and not holding and ready to buy. Transitions update profits accordingly. This prevents immediate rebuying.

Result

For prices [1,2,3,0,2], max profit is 3.

Modeling cooldown as states prevents illegal moves and captures real-world waiting periods.

6

Advanced

Transaction Fee Impact

🤔Before reading on: do you think fees reduce profit by a fixed amount per transaction or per day? Commit to your answer.

Concept: Subtract a fee from profit each time you sell.

Modify DP to subtract fee when selling. This changes when it's profitable to sell or hold. The fee discourages frequent trades.

Result

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

Incorporating fees models real costs and changes optimal trading frequency.

7

Expert

Optimizing Space and Time in DP Solutions

🤔Before reading on: do you think all DP states must be stored for all days? Commit to yes or no.

Concept: Use rolling arrays and state compression to reduce memory and speed up calculations.

Instead of storing full DP tables, keep only necessary previous states. Also, for large k, use greedy approach when k > n/2. This optimizes performance in practice.

Result

For large inputs, optimized DP runs faster and uses less memory without changing results.

Knowing when and how to optimize DP is crucial for scalable real-world applications.

Under the Hood

The core mechanism is dynamic programming that tracks states representing holding or not holding stock, number of transactions done, and cooldown or fees. Each day updates these states based on previous day states and price changes. This models all possible sequences of buy/sell actions efficiently.

Why designed this way?

These problems evolved from simple profit calculations to complex constraints reflecting real trading rules. DP was chosen because brute force checking all buy/sell sequences is exponential. DP breaks the problem into manageable subproblems with overlapping states.

Day i:
┌───────────────┐
│ States:       │
│ - hold stock  │
│ - no stock    │
│ - cooldown    │
│ - transactions│
└─────┬─────────┘
      │ updates based on price[i]
      ▼
Day i+1: same states updated

Transitions:
Hold -> Sell (profit + price - fee)
No stock -> Buy (profit - price)
Cooldown -> No stock

Myth Busters - 4 Common Misconceptions

Quick: Is summing all positive price differences always the best strategy for any number of transactions? Commit yes or no.

Common Belief: Summing all positive differences always gives max profit regardless of constraints.

Reality: This only works when unlimited transactions are allowed without fees or cooldowns.

Why it matters: Using this on limited transactions or with fees leads to wrong answers and lost profit.

Quick: Does buying and selling on the same day count as a valid transaction? Commit yes or no.

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

Reality: Usually, you must buy before you sell and cannot sell before buying; same-day buy and sell is not allowed.

Why it matters: Ignoring this leads to invalid solutions that overestimate profit.

Quick: Does adding a cooldown mean you cannot buy the day after selling? Commit yes or no.

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

Reality: Cooldown means you must skip one day after selling before buying again.

Why it matters: Misunderstanding cooldown causes incorrect state transitions and wrong profits.

Quick: For large k, is dynamic programming always necessary? Commit yes or no.

Common Belief: DP must be used for any number of transactions k.

Reality: If k is large (≥ n/2), the problem reduces to unlimited transactions and a greedy solution suffices.

Why it matters: Using DP unnecessarily wastes time and memory on large inputs.

Expert Zone

1

The order of state updates in DP matters; updating sell states before buy states avoids overwriting needed values.

2

When fees or cooldowns are added, the state machine grows, but careful state compression can keep complexity manageable.

3

For very large k, switching to a greedy approach is a key optimization that experts rely on to handle big data efficiently.

When NOT to use

These algorithms assume prices are known in advance (offline). For real-time streaming prices or unknown future, use online algorithms or reinforcement learning instead.

Production Patterns

In trading systems, these algorithms help build automated strategies for buying/selling with constraints like transaction limits, fees, and cooldowns. They also appear in interview questions testing dynamic programming skills.

Connections

Dynamic Programming

Builds-on

Understanding buy/sell stock problems deepens grasp of DP state modeling and transitions.

Knapsack Problem

Similar pattern

Both involve choosing items (transactions) under constraints to maximize value (profit).

Project Scheduling

Analogous constraint handling

Cooldown periods resemble mandatory waiting times between tasks, showing cross-domain constraint modeling.

Common Pitfalls

#1 Ignoring transaction limits and summing all positive differences.

Wrong approach:

int maxProfit(int* prices, int n) {
int profit = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i-1])
profit += prices[i] - prices[i-1];
}
return profit;
}

Correct approach:

Use DP to track transactions and states when limits exist, not just sum differences.

Root cause:

Misunderstanding that unlimited transactions assumption is required for simple summing.

#2 Allowing buy and sell on the same day.

Wrong approach:

if (prices[i] >= prices[i]) profit += prices[i] - prices[i]; // zero profit but invalid transaction

Correct approach:

Ensure buy day < sell day; no same-day transactions.

Root cause:

Confusing problem constraints about transaction order.

#3 Not accounting for cooldown day after selling.

Wrong approach:

After selling on day i, buying again on day i+1 without cooldown check.

Correct approach:

Track cooldown state and skip buying on cooldown days.

Root cause:

Ignoring problem rules about waiting periods.

Key Takeaways

Maximizing stock profit depends on carefully modeling buy/sell actions and constraints like transaction limits, cooldowns, and fees.

Simple summing of positive price differences only works when unlimited transactions are allowed without extra rules.

Dynamic programming is the main tool to solve complex variants by tracking states and transitions over days and transactions.

Optimizations like state compression and greedy shortcuts for large k improve performance in real applications.

Understanding these problems builds strong skills in planning, optimization, and constraint handling useful beyond stock trading.