Buy and Sell Stocks All Variants in DSA Typescript

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 have a fruit stand and prices change daily. You want to buy fruit when cheap and sell when expensive to earn money. Sometimes you can only buy and sell once, sometimes many times, and sometimes you pay a fee each time you sell.

Prices: [7] -> [1] -> [5] -> [3] -> [6] -> [4]
Buy low ↑          Sell high ↑

Dry Run Walkthrough

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

Goal: Maximize profit by buying and selling at most twice

Step 1: Start with no transactions and no stock

Day 0: price=7, profit=0, transactions=0

Why: Initialize before any buying or selling

Step 2: Buy at price 1 on day 1

Hold stock bought at 1, profit=0, transactions=0

Why: Buying low to prepare for selling high later

Step 3: Sell at price 5 on day 2 (first transaction)

Profit = 5 - 1 = 4, transactions=1, no stock held

Why: Sell to realize profit from first transaction

Step 4: Buy at price 3 on day 3

Hold stock bought at 3, profit=4, transactions=1

Why: Prepare for second transaction

Step 5: Sell at price 6 on day 4 (second transaction)

Profit = 4 + (6 - 3) = 7, transactions=2, no stock held

Why: Sell to realize profit from second transaction

Result:

Final profit = 7

Annotated Code

DSA Typescript

class StockTrader {
  prices: number[];
  maxTransactions: number;

  constructor(prices: number[], maxTransactions: number) {
    this.prices = prices;
    this.maxTransactions = maxTransactions;
  }

  maxProfit(): number {
    const n = this.prices.length;
    if (n === 0) return 0;

    // dp[t][d] = max profit up to day d with at most t transactions
    const dp: number[][] = Array.from({ length: this.maxTransactions + 1 }, () => Array(n).fill(0));

    for (let t = 1; t <= this.maxTransactions; t++) {
      let maxDiff = -this.prices[0];
      for (let d = 1; d < n; d++) {
        dp[t][d] = Math.max(dp[t][d - 1], this.prices[d] + maxDiff);
        maxDiff = Math.max(maxDiff, dp[t - 1][d - 1] - this.prices[d]);
      }
    }

    return dp[this.maxTransactions][n - 1];
  }
}

// Driver code
const prices = [7, 1, 5, 3, 6, 4];
const maxTransactions = 2;
const trader = new StockTrader(prices, maxTransactions);
console.log(trader.maxProfit());

const dp: number[][] = Array.from({ length: this.maxTransactions + 1 }, () => Array(n).fill(0));

Create a table to store max profit for each transaction count and day

for (let t = 1; t <= this.maxTransactions; t++) {

Iterate over number of transactions allowed

let maxDiff = -this.prices[0];

Track max difference between previous profits and price to optimize buying

dp[t][d] = Math.max(dp[t][d - 1], this.prices[d] + maxDiff);

Decide to sell today or skip selling

maxDiff = Math.max(maxDiff, dp[t - 1][d - 1] - this.prices[d]);

Update maxDiff to consider buying at current day

Output

7

Complexity Analysis

Time: O(n * k) because we fill a table with n days and k transactions

Space: O(n * k) for the dp table storing profits for each day and transaction count

vs Alternative: Naive approach tries all buy/sell pairs repeatedly, costing O(n^2 * k), so dp is much faster

Edge Cases

Empty prices array

Returns 0 profit immediately

DSA Typescript

if (n === 0) return 0;

Only one day of prices

No transactions possible, profit is 0

DSA Typescript

dp initialization and loop handle this naturally

Max transactions is 0

No trades allowed, profit is 0

DSA Typescript

dp array size and loops handle zero transactions case

When to Use This Pattern

When asked to maximize stock trading profit with limits on transactions or fees, use dynamic programming to track profits by day and transaction count.

Common Mistakes

Mistake: Trying to buy and sell on the same day or ignoring transaction limits
Fix: Use dp to track max profit with transaction count and ensure buy happens before sell

Summary

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

Use when you need to find best buy/sell strategy with limited transactions or fees.

Track profits by day and transaction count to avoid repeated calculations and ensure valid trades.