Buy and Sell Stocks All Variants in DSA Typescript - 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 given their prices over time. These problems vary by constraints like the number of transactions allowed, cooldown periods, or transaction fees. The goal is to find the best strategy to buy low and sell high under these rules. They teach how to optimize decisions over time using algorithms.

Why it matters

Without these strategies, investors might lose money by selling too early or buying too late. These problems model real-world trading challenges and teach how to make optimal decisions with limited resources or rules. Understanding them helps in financial planning, algorithmic trading, and dynamic programming skills. Without these concepts, one might miss out on maximizing gains or minimizing losses.

Where it fits

Before this, learners should know arrays, basic loops, and simple greedy algorithms. After mastering these, learners can explore dynamic programming deeply, optimization problems, and advanced financial algorithms. This topic bridges basic algorithmic thinking and complex decision-making under constraints.

Mental Model

Core Idea

Maximize profit by choosing the best days to buy and sell stocks under given constraints using optimal decision strategies.

Think of it like...

It's like planning when to buy and sell fruits at a market where prices change daily, but you have rules like limited buys or waiting days before selling again.

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

Constraints:
- Max transactions allowed
- Cooldown days after selling
- Transaction fees

Decision flow:
Day i: Buy? Sell? Hold? → Maximize profit

┌─────────────┐
│ Day i price │
└─────┬───────┘
      │
┌─────▼───────┐
│ Buy / Sell  │
└─────┬───────┘
      │
┌─────▼───────┐
│ Update Profit│
└─────────────┘

Build-Up - 7 Steps

1

Foundation

Single Transaction Maximum Profit

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

Given an array of prices, find the maximum difference between a later selling price and an earlier buying price. We track the minimum price seen so far and calculate potential profits by subtracting this from current prices.

Result

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

Understanding that tracking the minimum price so far lets you find the best single transaction profit efficiently.

2

Foundation

Multiple Transactions Without Restrictions

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

You can buy and sell multiple times. The best strategy is to sum all positive price differences between consecutive days. This captures every profitable rise.

Result

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

Knowing that summing all positive gains captures maximum profit when unlimited transactions are allowed.

3

Intermediate

At Most Two Transactions Allowed

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

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

We split the problem into two parts: max profit from day 0 to i, and max profit from day i to end. Then combine these to find max total profit with two transactions. This requires tracking profits forward and backward.

Result

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

Understanding that two transactions overlap and require combining forward and backward profit calculations.

4

Intermediate

K Transactions with Dynamic Programming

🤔Before reading on: do you think the time complexity grows linearly or quadratically with K? Commit to your answer.

Concept: Generalize to at most K transactions using DP with states tracking buys and sells.

Use a DP table where dp[i][j] is max profit up to day j with at most i transactions. Update dp using previous states and price differences. Optimizations reduce complexity.

Result

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

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

5

Intermediate

Cooldown Period After Selling

🤔Before reading on: do you think cooldown means you cannot buy or sell immediately after selling? Commit to your answer.

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

Use DP with states: holding stock, not holding and in cooldown, and not holding and free to buy. Update states each day considering cooldown constraints.

Result

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

Understanding cooldown adds a waiting state that changes when you can buy again.

6

Advanced

Transaction Fee Impact on Profit

🤔Before reading on: do you think fees apply on buying, selling, or both? Commit to your answer.

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

Modify DP states to subtract fee when selling. This changes the decision to sell or hold, as small profits may be negated by fees.

Result

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

Knowing fees discourage frequent trades and require careful sell timing.

7

Expert

Optimizing Space and Time for Large K

🤔Before reading on: do you think when K is large, the problem simplifies or becomes harder? Commit to your answer.

Concept: When K is large relative to days, problem reduces to unlimited transactions. Use this to optimize DP.

If K >= n/2 (n = days), treat as unlimited transactions and use simple sum of positive differences. Otherwise, use DP. This avoids expensive computations.

Result

For prices [1,2,3,4,5] and K=100, max profit is 4 (buy day 1 sell day 5).

Recognizing problem simplifications for large K saves computation and improves efficiency.

Under the Hood

These problems use dynamic programming to track states representing holding or not holding stock, number of transactions done, and cooldown or fee conditions. Each day updates these states based on previous day states and current price, ensuring optimal decisions. The DP tables or variables store max profit achievable under constraints, avoiding redundant calculations.

Why designed this way?

Stock trading problems model real-world constraints like limited trades, cooldowns, and fees. DP was chosen because greedy approaches fail when multiple transactions interact. The design balances complexity and efficiency, allowing solutions in polynomial time instead of exponential brute force.

Day i states:
┌───────────────┐
│ Holding stock │
│ Not holding + │
│ cooldown      │
│ Not holding   │
│ free to buy   │
└──────┬────────┘
       │
       ▼
Update states with price[i] and constraints
       │
       ▼
Max profit so far

Transitions:
Holding[i] = max(Holding[i-1], NotHoldingFree[i-1] - price[i])
NotHoldingCooldown[i] = Holding[i-1] + price[i] - fee
NotHoldingFree[i] = max(NotHoldingFree[i-1], NotHoldingCooldown[i-1])

Myth Busters - 4 Common Misconceptions

Quick: Is the best strategy always to buy at the lowest price and sell at the highest price overall? Commit to yes or no.

Common Belief: Buy at the lowest price and sell at the highest price overall to maximize profit.

Reality: You must buy before you sell, so the highest price must come after the lowest price. Sometimes the lowest price is after the highest price, so you can't just pick extremes.

Why it matters: Ignoring order leads to invalid trades and wrong profit calculations.

Quick: Does allowing unlimited transactions always increase profit compared to one transaction? Commit to yes or no.

Common Belief: More transactions always mean more profit.

Reality: If prices only decrease or stay flat, multiple transactions yield no profit. Also, fees or cooldowns can reduce profit despite more transactions.

Why it matters: Assuming more trades always help can cause losses or wasted effort.

Quick: Does cooldown mean you cannot sell on consecutive days? Commit to yes or no.

Common Belief: Cooldown means you cannot sell stocks on consecutive days.

Reality: Cooldown applies after selling, preventing buying the next day, but you can sell on consecutive days if you already hold stocks.

Why it matters: Misunderstanding cooldown leads to wrong state transitions and suboptimal profits.

Quick: When K is very large, do you still need complex DP? Commit to yes or no.

Common Belief: You always need complex DP regardless of K.

Reality: When K >= n/2, problem reduces to unlimited transactions, solvable with a simple linear scan.

Why it matters: Not using this shortcut wastes time and resources on large inputs.

Expert Zone

1

Tracking states with minimal variables instead of full DP tables can optimize space from O(nK) to O(K).

2

Transaction fees and cooldowns can be combined by carefully adjusting state transitions, but this increases complexity.

3

Edge cases like constant prices or strictly decreasing prices require careful handling to avoid false profits.

When NOT to use

These algorithms assume perfect knowledge of future prices, which is unrealistic in real markets. For real-time trading, probabilistic models or machine learning approaches are better. Also, for very large K and long time series, heuristic or approximate methods may be preferred.

Production Patterns

Used in algorithmic trading bots to decide buy/sell signals under constraints. Also common in coding interviews to test dynamic programming skills. Variants appear in financial modeling software to simulate trading strategies.

Connections

Dynamic Programming

Builds-on

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

Greedy Algorithms

Opposite

Comparing greedy and DP approaches clarifies when local optimal choices fail and global optimization is needed.

Project Management Scheduling

Similar pattern

Both involve optimizing sequences of actions under constraints like cooldowns or limited resources, showing cross-domain optimization parallels.

Common Pitfalls

#1 Trying to buy and sell on the same day.

Wrong approach:

for(let i=0; i

Correct approach:

Track buy day before sell day; ensure buy index < sell index.

Root cause:

Misunderstanding that transactions require buying before selling.

#2 Ignoring cooldown and buying immediately after selling.

Wrong approach:

dp[i][holding] = max(dp[i-1][holding], dp[i-1][notHolding] - price[i]); // no cooldown check

Correct approach:

dp[i][holding] = max(dp[i-1][holding], dp[i-2][notHolding] - price[i]); // cooldown enforced

Root cause:

Not modeling cooldown state properly in DP transitions.

#3 Applying transaction fee on buying instead of selling.

Wrong approach:

dp[i][holding] = max(dp[i-1][holding], dp[i-1][notHolding] - price[i] - fee);

Correct approach:

dp[i][notHolding] = max(dp[i-1][notHolding], dp[i-1][holding] + price[i] - fee);

Root cause:

Confusing when fees apply in transactions.

Key Takeaways

Maximizing stock trading profit requires careful tracking of buy and sell decisions respecting constraints like transaction limits, cooldowns, and fees.

Dynamic programming models these problems by representing states of holding or not holding stocks and updating profits day by day.

Simplifications exist when constraints are relaxed, such as unlimited transactions reducing complexity to summing positive gains.

Misunderstanding order of transactions, cooldown rules, or fee application leads to incorrect solutions.

Recognizing problem variants and constraints helps choose the right algorithm and optimize performance.