Buy and Sell Stocks All Variants in DSA Go - 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 rules like how many transactions you can make or if you must wait between trades. 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 trades to get the most profit. In real life, this means better financial decisions and less risk. Without this knowledge, people might miss chances to grow their money or lose it unnecessarily.

Where it fits

Before this, you should know basic arrays and simple loops. After this, you can learn dynamic programming deeply and other optimization problems. This topic builds your skills in planning and decision-making algorithms.

Mental Model

Core Idea

Maximize profit by choosing the best buy and sell days under given rules using smart tracking of prices and transactions.

Think of it like...

It's like buying fruits at a market: you want to buy when prices are low and sell when prices are high, but sometimes you can only buy and sell a few times or must wait between trades.

Prices:  7 ──┐        ┌── 5 ──┐        ┌── 3 ──┐
          │   └── 1 ──┘    │   └── 6 ──┘    │   └── 4 ──┘
Days:    0    1    2    3    4    5    6    7    8    9
Buy low here -> ↑          Sell high here -> ↑

Build-Up - 7 Steps

1

Foundation

Single Transaction Maximum Profit

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

We scan prices from left to right, keeping track of the lowest price seen so far. For each day, we calculate profit if we sell today (current price - lowest price). We update max profit if this is better. This finds the best single buy-sell pair.

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 on the fly is the base for all stock problems.

2

Foundation

Unlimited Transactions Profit

Concept: Calculate max profit when you can buy and sell as many times as you want.

We add up all positive price differences between consecutive days. This simulates buying before every rise and selling at the peak. No need to track minimum price here, just sum gains.

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 rises equals max profit when unlimited trades allowed simplifies the problem greatly.

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: Maximize profit with at most two buy-sell pairs using dynamic programming.

We split the array into two parts at every day. For each day, we find max profit from 0 to that day (one transaction) and from that day to end (one transaction). Adding these gives max profit with two transactions. We keep track of max overall.

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

Splitting the problem into two parts and combining results shows how to handle multiple transactions efficiently.

4

Intermediate

K Transactions Maximum Profit

🤔Before reading on: do you think the solution for k transactions is just repeating the two transactions method k times? Commit to yes or no.

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

We use a 2D DP array where dp[t][d] is max profit with t transactions until day d. For each t and d, we track max of dp[t][d-1] and price[d] + maxDiff, where maxDiff = max(dp[t-1][m] - price[m]) for m < d. This avoids nested loops.

Result

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

Tracking maxDiff lets us avoid slow nested loops and efficiently compute max profit for any k.

5

Intermediate

Cooldown Period Between Transactions

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

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

We track three states: hold (holding stock), sold (just sold), and rest (not holding, cooldown or idle). Transitions: hold = max(hold, rest - price), sold = hold + price, rest = max(rest, sold_prev). Max profit is max(sold, rest).

Result

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

Modeling cooldown as a separate state clarifies how waiting affects profit.

6

Advanced

Transaction Fee Impact

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

Concept: Incorporate a fixed fee cost per transaction into profit calculations.

Modify hold state update to subtract fee when buying: hold = max(hold, rest - price - fee). Selling adds price to sold state as usual. This reduces profit by fee per buy-sell pair.

Result

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

Including fees changes when it is profitable to trade, teaching cost-benefit analysis.

7

Expert

Optimizing Space and Time Complexity

🤔Before reading on: do you think all DP solutions require O(k*n) space and time? Commit to yes or no.

Concept: Use rolling arrays and variables to reduce space from O(k*n) to O(n) and optimize time.

Instead of storing full dp arrays, keep track of current and previous transaction states with variables. For large k, if k > n/2, treat as unlimited transactions to simplify. This reduces complexity and speeds up execution.

Result

For large inputs, optimized code runs faster and uses less memory.

Recognizing problem limits and using space optimization techniques is key for production-ready solutions.

Under the Hood

These problems use dynamic programming to track states representing holding or not holding stock, number of transactions done, and cooldown or fees. The algorithm updates these states day by day, using previous results to avoid recomputation. This relies on the principle of optimal substructure: the best solution up to today depends on best solutions before today.

Why designed this way?

Stock trading problems model real-world constraints like limited trades, cooldowns, and fees. Dynamic programming fits because it breaks complex decisions into simpler overlapping subproblems. Alternatives like brute force are too slow. The state-based design balances clarity and efficiency.

┌─────────────┐      ┌─────────────┐      ┌─────────────┐
│  Hold State │─────▶│ Sold State  │─────▶│  Rest State │
└─────────────┘      └─────────────┘      └─────────────┘
      ▲                    │                    │
      │                    ▼                    ▼
      └────────────────────────────────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Is buying and selling multiple times always better than one transaction? Commit yes or no.

Common Belief: More transactions always mean more profit.

Reality: Sometimes fewer transactions yield better profit due to fees or cooldowns.

Why it matters: Ignoring costs or cooldowns can lead to strategies that lose money in real trading.

Quick: Does the best buy day always come before the best sell day? Commit yes or no.

Common Belief: The lowest price day is always the best buy day.

Reality: The lowest price might be too early or followed by even lower prices; timing matters.

Why it matters: Buying too early without considering future prices can reduce profit.

Quick: Can you solve k transactions problem by just repeating single transaction solution k times? Commit yes or no.

Common Belief: Solving single transaction multiple times solves k transactions problem.

Reality: Transactions overlap and affect each other; dynamic programming is needed.

Why it matters: Naive repetition leads to incorrect profit calculations and wrong answers.

Quick: Does cooldown mean you cannot sell two days in a row? Commit yes or no.

Common Belief: Cooldown prevents selling on consecutive days.

Reality: Cooldown prevents buying immediately after selling, not selling itself.

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

Expert Zone

1

Tracking maxDiff in k transactions DP is a subtle optimization that avoids nested loops and speeds up computation.

2

For very large k, treating the problem as unlimited transactions is a key shortcut that experts use.

3

State machines modeling hold, sold, and rest states elegantly handle cooldown and fees, simplifying complex constraints.

When NOT to use

These algorithms assume perfect knowledge of future prices, which is unrealistic in real markets. For real-time trading, use probabilistic models or machine learning. Also, if transaction costs vary or prices are not discrete, these models need adjustment.

Production Patterns

In production, these patterns appear in algorithmic trading bots, portfolio optimization, and financial simulations. Experts combine these DP solutions with risk management and real-time data feeds.

Connections

Dynamic Programming

Builds-on

Understanding stock problems deepens grasp of DP by applying it to real-world sequential decision making.

State Machines

Same pattern

Modeling buy/sell/hold as states shows how state machines solve complex constraints elegantly.

Economics - Supply and Demand

Analogous pattern

Stock price fluctuations reflect supply and demand dynamics, linking algorithmic decisions to economic principles.

Common Pitfalls

#1 Ignoring transaction fees in profit calculation.

Wrong approach:

hold = max(hold, rest - price)
sold = hold + price
rest = max(rest, sold_prev)

Correct approach:

hold = max(hold, rest - price - fee)
sold = hold + price
rest = max(rest, sold_prev)

Root cause:

Forgetting to subtract fees when buying leads to overestimating profit.

#2 Using nested loops for k transactions without optimization.

Wrong approach:

for t in 1..k {
for d in 1..n {
for m in 0..d-1 {
dp[t][d] = max(dp[t][d], dp[t-1][m] + price[d] - price[m])
}
}
}

Correct approach:

for t in 1..k {
maxDiff = -price[0]
for d in 1..n {
dp[t][d] = max(dp[t][d-1], price[d] + maxDiff)
maxDiff = max(maxDiff, dp[t-1][d] - price[d])
}
}

Root cause:

Not using maxDiff optimization causes slow, inefficient code.

#3 Misunderstanding cooldown as preventing selling on consecutive days.

Wrong approach:

sold = max(sold, sold_prev) // disallow selling two days in a row

Correct approach:

sold = hold + price
rest = max(rest, sold_prev) // cooldown prevents buying immediately after selling

Root cause:

Confusing cooldown rules leads to wrong state updates and profits.

Key Takeaways

Maximizing stock profit involves tracking buy and sell decisions carefully under given constraints.

Dynamic programming breaks down complex trading rules into manageable states and transitions.

Optimizations like tracking maxDiff and recognizing unlimited transactions cases improve efficiency.

Understanding cooldowns and fees as states prevents common mistakes in profit calculation.

These problems connect algorithmic thinking with real-world financial decision making.

Practice

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

easy

A. Find the day with the highest stock price only

B. Minimize the number of transactions regardless of profit

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 goal

   The problem asks to maximize profit by buying and selling stocks on certain days.

2. Step 2: Identify the correct objective

   Maximizing profit means choosing days to buy low and sell high, not just counting transactions or prices.

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 prices or counts [OK]

Common Mistakes:

• Confusing profit with number of transactions
• Thinking only about highest price day
• Ignoring the buy day in calculations

2. Which of the following Go code snippets correctly initializes a slice to store stock prices for 5 days?

easy

A. prices := []int{7, 1, 5, 3, 6}

B. prices := [5]int{7, 1, 5, 3, 6}

C. prices := make([]int, 5, 5)

D. prices := new([]int{7, 1, 5, 3, 6})

Solution

1. Step 1: Understand slice initialization in Go

   To create a slice with values, use the literal syntax: []int{values}.

2. Step 2: Check each option

   prices := []int{7, 1, 5, 3, 6} correctly creates a slice with given values. prices := [5]int{7, 1, 5, 3, 6} creates an array, not a slice. prices := make([]int, 5, 5) creates an empty slice of length 5 but no values. prices := new([]int{7, 1, 5, 3, 6}) is invalid syntax.

3. Final Answer:

   prices := []int{7, 1, 5, 3, 6} -> Option A

4. Quick Check:

   Slice literal = []int{values} [OK]

Hint: Use []int{...} to create slices with values directly [OK]

Common Mistakes:

• Using array syntax instead of slice
• Using new() incorrectly for slices
• Creating empty slices without values

3. What is the output of the following Go code that finds the max profit with only one transaction?

func maxProfit(prices []int) int {
    minPrice := prices[0]
    maxProfit := 0
    for _, price := range prices {
        if price < minPrice {
            minPrice = price
        } else if price - minPrice > maxProfit {
            maxProfit = price - minPrice
        }
    }
    return maxProfit
}

fmt.Println(maxProfit([]int{7,1,5,3,6,4}))

medium

A. 5

B. 6

C. 4

D. 7

Solution

1. Step 1: Trace the loop to find minPrice and maxProfit

   Start minPrice=7, maxProfit=0. Iterate prices: - price=7: minPrice=7, maxProfit=0 - price=1: minPrice=1 (lower) - price=5: profit=5-1=4 >0, maxProfit=4 - price=3: profit=3-1=2 <4, maxProfit=4 - price=6: profit=6-1=5 >4, maxProfit=5 - price=4: profit=4-1=3 <5, maxProfit=5

2. Step 2: Return maxProfit

   maxProfit is 5 after loop ends.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Max profit = 5 [OK]

Hint: Track min price and update max profit during iteration [OK]

Common Mistakes:

• Not updating minPrice correctly
• Calculating profit before updating minPrice
• Returning wrong variable

4. Identify the bug in this Go function that tries to calculate max profit with unlimited transactions:

func maxProfit(prices []int) int {
    profit := 0
    for i := 0; i < len(prices); i++ {
        if prices[i] > prices[i-1] {
            profit += prices[i] - prices[i-1]
        }
    }
    return profit
}

medium

A. prices slice is not initialized

B. Incorrect profit calculation logic

C. Missing return statement

D. Index out of range error due to accessing prices[i-1] when i=0

Solution

1. Step 1: Check loop and index usage

   The loop starts at i=0, but code accesses prices[i-1], which is prices[-1] at i=0, causing index out of range error.

2. Step 2: Identify fix

   Start loop from i=1 to avoid negative index access.

3. Final Answer:

   Index out of range error due to accessing prices[i-1] when i=0 -> Option D

4. Quick Check:

   Loop index must start at 1 to avoid error [OK]

Hint: Avoid negative indices by starting loop at 1 [OK]

Common Mistakes:

• Starting loop at 0 but accessing i-1
• Ignoring runtime errors
• Not testing with small input arrays

5. Given the prices [3, 3, 5, 0, 0, 3, 1, 4], what is the maximum profit with at most two transactions?

hard

A. 7

B. 6

C. 5

D. 8

Solution

1. Step 1: Understand two transactions limit

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

2. Step 2: Calculate max profit with two transactions

   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

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Two transactions max profit = 6 [OK]

Hint: Split array, find max profit left and right, sum max [OK]

Common Mistakes:

• Counting overlapping transactions
• Ignoring zero price days
• Calculating only one transaction profit