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.

Practice

1. What is the main goal when solving the Buy and Sell Stocks problem with only one transaction allowed?

easy

A. Maximize the difference between a later selling price and an earlier buying price

B. Minimize the number of transactions

C. Find the lowest price in the array

D. Calculate the average stock price

Solution

1. Step 1: Understand the problem goal

   The problem asks to find the maximum profit by buying and selling once, so we want the biggest positive difference between a sell price after a buy price.

2. Step 2: Identify the correct approach

   Maximizing the difference between a later selling price and an earlier buying price directly solves the problem.

3. Final Answer:

   Maximize the difference between a later selling price and an earlier buying price -> Option A

4. Quick Check:

   Goal = Maximize profit from one buy and one sell [OK]

Hint: Look for max difference with sell after buy [OK]

Common Mistakes:

• Thinking to minimize transactions instead of maximizing profit
• Confusing lowest price with max profit
• Ignoring the order of buy before sell

2. Which of the following TypeScript function signatures correctly represents a function to find max profit from multiple stock transactions?

easy

A. function maxProfit(prices: number[]): number

B. function maxProfit(prices: string): number[]

C. function maxProfit(prices: number): string

D. function maxProfit(prices: any): void

Solution

1. Step 1: Analyze the input and output types

   The input should be an array of numbers representing prices, so prices: number[]. The output is the maximum profit, a number.

2. Step 2: Match the correct function signature

   function maxProfit(prices: number[]): number matches input as number array and output as number, which is correct.

3. Final Answer:

   function maxProfit(prices: number[]): number -> Option A

4. Quick Check:

   Input array, output number [OK]

Hint: Input array of numbers, output single number [OK]

Common Mistakes:

• Using string type for prices
• Returning array instead of number
• Using void return type

3. What is the output of the following TypeScript code for max profit with unlimited transactions?

function maxProfit(prices: number[]): number {
  let profit = 0;
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }
  return profit;
}

console.log(maxProfit([7,1,5,3,6,4]));

medium

A. 5

B. 7

C. 8

D. 6

Solution

1. Step 1: Trace the loop and calculate profit increments

   Prices: [7,1,5,3,6,4] - i=1: 1 > 7? No, profit=0 - i=2: 5 > 1? Yes, profit += 5-1=4 - i=3: 3 > 5? No, profit=4 - i=4: 6 > 3? Yes, profit += 6-3=3, total=7 - i=5: 4 > 6? No, profit=7

2. Step 2: Return total profit

   Total profit after loop is 7.

3. Final Answer:

   7 -> Option B

4. Quick Check:

   Sum of positive diffs = 7 [OK]

Hint: Add all positive price differences [OK]

Common Mistakes:

• Adding negative differences
• Only considering one transaction
• Misreading array indices

4. Identify the bug in this TypeScript code for max profit with one transaction:

function maxProfit(prices: number[]): number {
  let minPrice = prices[0];
  let maxProfit = 0;
  for (let i = 1; i <= prices.length; i++) {
    if (prices[i] < minPrice) {
      minPrice = prices[i];
    } else if (prices[i] - minPrice > maxProfit) {
      maxProfit = prices[i] - minPrice;
    }
  }
  return maxProfit;
}

medium

A. prices array should be sorted first

B. minPrice should be initialized to 0

C. maxProfit should start at -Infinity

D. Loop condition should be < instead of <=

Solution

1. Step 1: Check loop boundary

   The loop runs with i from 1 to prices.length inclusive, but array indices go from 0 to prices.length - 1. Using <= causes out-of-bounds access at prices[prices.length].

2. Step 2: Correct the loop condition

   Change loop condition to i < prices.length to avoid accessing undefined elements.

3. Final Answer:

   Loop condition should be < instead of <= -> Option D

4. Quick Check:

   Array index out-of-bounds fixed by < condition [OK]

Hint: Use < for array loops, not <= [OK]

Common Mistakes:

• Using <= causing runtime errors
• Initializing minPrice incorrectly
• Sorting prices unnecessarily

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. 5

B. 6

C. 7

D. 4

Solution

1. Step 1: Understand two transactions limit

   We can buy and sell at most twice. We want to split the array into two parts and maximize profit from each.

2. Step 2: Calculate max profit for each split

   Best first transaction: buy at 3, sell at 5 = 2 profit Best second transaction: buy at 0, sell at 4 = 4 profit Total max profit = 2 + 4 = 6

3. Step 3: Check for better splits

   Splitting at index 5: first part max profit = 4 (buy at 0 sell at 3), second part max profit = 3 (buy at 1 sell at 4), total = 7

4. Final Answer:

   7 -> Option C

5. Quick Check:

   Sum of two best transactions = 7 [OK]

Hint: Split array, sum max profits from two parts [OK]

Common Mistakes:

• Counting more than two transactions
• Not splitting array correctly
• Choosing wrong buy/sell days