Buy and Sell Stocks All Variants in DSA Python - Deep Dive

Overview - Buy and Sell Stocks All Variants

What is it?

Buying and selling stocks problems involve deciding the best times to buy and sell stocks to maximize profit. These problems use arrays where each element represents the stock price on a given day. The goal is to find the best strategy to buy low and sell high, sometimes with constraints like limited transactions or cooldown periods. They help us understand how to optimize decisions over time with changing values.

Why it matters

Without these strategies, investors might lose money by buying or selling at the wrong times. These problems teach how to make smart choices in uncertain, changing environments, which applies beyond stocks to many real-life decisions involving timing and resource management. They also build skills in dynamic programming and greedy algorithms, which are widely used in software and finance.

Where it fits

Before this, learners should understand arrays, basic loops, and simple greedy algorithms. After mastering these variants, learners can explore advanced dynamic programming, sliding window techniques, and optimization problems in finance and operations research.

Mental Model

Core Idea

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

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

┌─────┬─────┬─────┬─────┬─────┬─────┐
│  7  │  1  │  5  │  3  │  6  │  4  │
└─────┴─────┴─────┴─────┴─────┴─────┘
  Day1  Day2  Day3  Day4  Day5  Day6

Build-Up - 7 Steps

1

Foundation

Single Transaction Maximum Profit

Concept: Find the best single buy-sell pair to maximize profit.

Given an array of prices, we want to buy once and sell once later. We track the lowest price seen so far and calculate potential profit by selling at the current price. We update the max profit if this is better. Example code: prices = [7,1,5,3,6,4] min_price = float('inf') max_profit = 0 for price in prices: if price < min_price: min_price = price elif price - min_price > max_profit: max_profit = price - min_price print(max_profit)

Result

5

Understanding that tracking the lowest price so far lets us find the best profit in one pass is key to efficient solutions.

2

Foundation

Unlimited Transactions Profit

Concept: Maximize profit by buying and selling multiple times without limits.

We can buy and sell as many times as we want, but we must sell before buying again. The best strategy is to add up all positive price differences between consecutive days. Example code: prices = [7,1,5,3,6,4] profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1] print(profit)

Result

7

Summing all upward price changes captures all profitable trades without complex tracking.

3

Intermediate

At Most Two Transactions

🤔Before reading on: do you think tracking two separate profits or combining all profits works better? Commit to your answer.

Concept: Limit the number of buy-sell pairs to two to maximize profit.

We split the problem into two parts: max profit from day 0 to i, and max profit from day i to end. We compute two arrays: - left_profits: max profit up to day i - right_profits: max profit from day i to end Then combine them to find max total profit. Example code: prices = [3,3,5,0,0,3,1,4] left_profits = [0]*len(prices) right_profits = [0]*len(prices) min_price = prices[0] for i in range(1, len(prices)): min_price = min(min_price, prices[i]) left_profits[i] = max(left_profits[i-1], prices[i] - min_price) max_price = prices[-1] for i in range(len(prices)-2, -1, -1): max_price = max(max_price, prices[i]) right_profits[i] = max(right_profits[i+1], max_price - prices[i]) max_profit = 0 for i in range(len(prices)): max_profit = max(max_profit, left_profits[i] + right_profits[i]) print(max_profit)

Result

6

Breaking the problem into two halves and combining results allows handling transaction limits efficiently.

4

Intermediate

K Transactions Using Dynamic Programming

🤔Before reading on: do you think a greedy or DP approach handles k transactions better? Commit to your answer.

Concept: Use dynamic programming to handle any number k of allowed transactions.

We use a DP table where dp[t][d] is max profit using at most t transactions until day d. Transition: For each transaction t and day d: dp[t][d] = max(dp[t][d-1], max(prices[d] - prices[m] + dp[t-1][m]) for m < d) To optimize, track max_diff = max(dp[t-1][m] - prices[m]) while iterating days. Example code: k = 2 prices = [3,2,6,5,0,3] if not prices or k == 0: print(0) exit() if k >= len(prices)//2: profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1] print(profit) exit() dp = [[0]*len(prices) for _ in range(k+1)] for t in range(1, k+1): max_diff = -prices[0] for d in range(1, len(prices)): dp[t][d] = max(dp[t][d-1], prices[d] + max_diff) max_diff = max(max_diff, dp[t-1][d] - prices[d]) print(dp[k][-1])

Result

7

Dynamic programming with careful state tracking efficiently solves complex transaction limits.

5

Intermediate

Cooldown Period Between Transactions

🤔Before reading on: do you think cooldown means skipping days or limiting transactions? Commit to your answer.

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

We track three states per day: - hold: max profit holding a stock - sold: max profit just sold stock - rest: max profit doing nothing Transitions: hold[i] = max(hold[i-1], rest[i-1] - prices[i]) sold[i] = hold[i-1] + prices[i] rest[i] = max(rest[i-1], sold[i-1]) Example code: prices = [1,2,3,0,2] hold = [0]*len(prices) sold = [0]*len(prices) rest = [0]*len(prices) hold[0] = -prices[0] for i in range(1, len(prices)): hold[i] = max(hold[i-1], rest[i-1] - prices[i]) sold[i] = hold[i-1] + prices[i] rest[i] = max(rest[i-1], sold[i-1]) print(max(sold[-1], rest[-1]))

Result

3

Modeling cooldown as separate states captures the waiting period constraint cleanly.

6

Advanced

Transaction Fee Impact on Profit

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

Concept: Subtract a fixed fee from each sell to model transaction costs.

We modify the hold and sold states to subtract fee when selling. Transitions: hold[i] = max(hold[i-1], sold[i-1] - prices[i]) sold[i] = max(sold[i-1], hold[i-1] + prices[i] - fee) Example code: prices = [1,3,2,8,4,9] fee = 2 hold = -prices[0] sold = 0 for i in range(1, len(prices)): prev_hold = hold hold = max(hold, sold - prices[i]) sold = max(sold, prev_hold + prices[i] - fee) print(sold)

Result

8

Incorporating fees changes the decision to sell, requiring careful state updates.

7

Expert

Optimizing Space and Time Complexity

🤔Before reading on: do you think storing full DP tables is necessary for all variants? Commit to your answer.

Concept: Use rolling variables and greedy shortcuts to reduce memory and speed up computations.

Many DP solutions only need previous states, so we keep variables instead of full tables. For example, in k transactions, if k is large, treat as unlimited transactions. Also, greedy summing of positive differences works when no constraints. Example code for unlimited transactions: prices = [7,1,5,3,6,4] profit = 0 for i in range(1, len(prices)): profit += max(0, prices[i] - prices[i-1]) print(profit) For k transactions, keep arrays of size k+1 for hold and sold states instead of full dp table.

Result

7

Recognizing when to simplify DP to greedy or rolling variables saves resources and improves performance.

Under the Hood

These problems model stock trading as state transitions over time, where each day represents a state with possible actions: buy, sell, or hold. Dynamic programming stores intermediate results to avoid recomputation, tracking profits under constraints like transaction limits or cooldowns. The algorithm updates states based on previous states and current prices, ensuring optimal decisions at each step.

Why designed this way?

Stock trading involves sequential decisions with dependencies on past actions. Early greedy solutions worked only for simple cases. Dynamic programming was introduced to handle complex constraints efficiently by breaking the problem into overlapping subproblems. This approach balances time complexity and memory use, enabling practical solutions for real-world scenarios.

Day i-1 States       Day i States
┌───────────────┐    ┌───────────────┐
│ hold[i-1]     │───▶│ hold[i]       │
│ sold[i-1]     │───▶│ sold[i]       │
│ rest[i-1]     │───▶│ rest[i]       │
└───────────────┘    └───────────────┘
Transitions depend on prices[i] and previous states, updating profits accordingly.

Myth Busters - 4 Common Misconceptions

Quick: Is buying and selling on the same day allowed for profit? Commit yes or no.

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

Reality: You must buy before you sell, so buying and selling on the same day is not allowed.

Why it matters: Assuming same-day transactions leads to incorrect profit calculations and invalid strategies.

Quick: Does more transactions always mean more profit? Commit yes or no.

Common Belief: More transactions always increase profit.

Reality: Transaction limits, fees, and cooldowns can reduce profit if too many trades are made.

Why it matters: Ignoring constraints causes overtrading and lower actual profits.

Quick: Does summing all positive differences always give max profit? Commit yes or no.

Common Belief: Adding all positive price differences always yields max profit.

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

Why it matters: Applying this to constrained problems gives wrong answers and poor strategies.

Quick: Is dynamic programming always necessary for stock problems? Commit yes or no.

Common Belief: Dynamic programming is always needed for stock trading problems.

Reality: Simple cases can be solved greedily; DP is needed only for constraints like limited transactions or cooldowns.

Why it matters: Overusing DP leads to unnecessary complexity and slower solutions.

Expert Zone

1

Tracking states like hold, sold, and rest separately allows modeling complex constraints elegantly.

2

Recognizing when k is large enough to treat as unlimited transactions simplifies algorithms drastically.

3

Optimizing DP with rolling arrays or variables reduces memory from O(k*n) to O(k), critical for large inputs.

When NOT to use

Avoid DP for very large k when it exceeds half the number of days; use greedy instead. For real-time trading, these offline algorithms are not suitable; use streaming or heuristic methods.

Production Patterns

Used in financial software for backtesting trading strategies, risk management, and algorithmic trading. Also appears in coding interviews to test understanding of DP and greedy algorithms.

Connections

Dynamic Programming

Builds-on

Understanding stock problems deepens grasp of DP state transitions and optimization.

Greedy Algorithms

Opposite approach

Knowing when greedy works versus DP helps choose efficient solutions.

Operations Research

Application domain

Stock trading optimization shares principles with resource allocation and scheduling problems.

Common Pitfalls

#1 Ignoring transaction fees and overestimating profit.

Wrong approach:

profit += prices[i] - prices[i-1] # without subtracting fee

Correct approach:

if prices[i] - prices[i-1] > fee:
profit += prices[i] - prices[i-1] - fee

Root cause:

Not accounting for costs reduces real profit and leads to wrong decisions.

#2 Allowing multiple buys without selling first.

Wrong approach:

buy on day 1, buy again on day 2 without selling

Correct approach:

buy on day 1, sell before buying again on day 2

Root cause:

Misunderstanding that you can hold only one stock at a time.

#3 Using full DP tables when only previous states are needed, wasting memory.

Wrong approach:

dp = [[0]*n for _ in range(k+1)] # storing all states

Correct approach:

Use rolling arrays or variables to store only needed previous states.

Root cause:

Not recognizing overlapping subproblems and state dependencies.

Key Takeaways

Maximizing stock trading profit involves choosing the best buy and sell days under given constraints.

Simple cases can be solved greedily by summing positive price differences, but constraints require dynamic programming.

Tracking states like holding, selling, and resting models complex rules like cooldowns and fees effectively.

Optimizing space and time by using rolling variables and recognizing problem limits improves real-world performance.

Understanding these variants builds strong skills in algorithm design, useful beyond stock problems.

Practice

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

easy

A. Find the day with the lowest 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 find the best days to buy and sell stocks to get the highest profit.

2. Step 2: Identify the objective

   Maximizing profit means buying low and selling high at the right times.

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:

• Thinking the goal is to minimize transactions
• Only finding lowest price day without selling
• Calculating averages instead of profit

2. Which of the following Python code snippets correctly initializes variables to track minimum price and maximum profit for the stock problem?

easy

A. min_price = float('inf'); max_profit = 0

B. min_price = 0; max_profit = float('-inf')

C. min_price = None; max_profit = None

D. min_price = 0; max_profit = 0

Solution

1. Step 1: Understand initialization needs

   We want min_price to start very high so any price is lower, and max_profit to start at zero.

2. Step 2: Check each option

   min_price = float('inf'); max_profit = 0 sets min_price to infinity and max_profit to zero, which is correct for tracking minimum and maximum values.

3. Final Answer:

   min_price = float('inf'); max_profit = 0 -> Option A

4. Quick Check:

   Initialization = min_price high, max_profit zero [OK]

Hint: Use infinity for min_price start, zero for max_profit [OK]

Common Mistakes:

• Setting min_price to zero causes wrong minimum tracking
• Using None without checks causes errors
• Setting max_profit to negative infinity can confuse logic

3. What is the output of the following code snippet for prices = [7,1,5,3,6,4]?

min_price = float('inf')
max_profit = 0
for price in prices:
    if price < min_price:
        min_price = price
    elif price - min_price > max_profit:
        max_profit = price - min_price
print(max_profit)

medium

A. 6

B. 7

C. 4

D. 5

Solution

1. Step 1: Trace the loop with given prices

   Prices: 7,1,5,3,6,4 - Start min_price=inf, max_profit=0 - price=7: min_price=7 - price=1: min_price=1 (lower) - price=5: profit=5-1=4 > 0, max_profit=4 - price=3: profit=3-1=2 < 4, no change - price=6: profit=6-1=5 > 4, max_profit=5 - price=4: profit=4-1=3 < 5, no change

2. Step 2: Final max_profit after loop

   max_profit is 5 after checking all prices.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Max profit = 5 [OK]

Hint: Track min price and update max profit on higher prices [OK]

Common Mistakes:

• Confusing max profit with max price
• Not updating min_price correctly
• Calculating profit incorrectly

4. Identify the error in this code snippet for the stock problem:

prices = [7,1,5,3,6,4]
min_price = 0
max_profit = 0
for price in prices:
    if price < min_price:
        min_price = price
    elif price - min_price > max_profit:
        max_profit = price - min_price
print(max_profit)

medium

A. Loop should start from second element

B. min_price initialized to 0 instead of a high value

C. max_profit should start at float('inf')

D. Using elif instead of if causes logic error

Solution

1. Step 1: Check variable initialization

   min_price is set to 0, but prices include values greater than 0, so min_price never updates to actual minimum (1).

2. Step 2: Effect of wrong min_price initialization

   Since min_price=0, price < min_price is never true, so min_price stays 0, causing incorrect profit calculations.

3. Final Answer:

   min_price initialized to 0 instead of a high value -> Option B

4. Quick Check:

   min_price must start high to track minimum [OK]

Hint: Initialize min_price to infinity, not zero [OK]

Common Mistakes:

• Starting min_price at zero causes wrong minimum tracking
• Confusing max_profit initialization
• Thinking elif causes logic error here

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

B. 7

C. 5

D. 4

Solution

1. Step 1: Understand two transactions limit

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

2. Step 2: Calculate profits for two transactions

   First transaction: buy at 3, sell at 5 = 2 profit Second transaction: buy at 0, sell at 4 = 4 profit Total profit = 2 + 4 = 6

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Two transactions max profit = 6 [OK]

Hint: Split array, find max profit in two parts [OK]

Common Mistakes:

• Counting overlapping transactions
• Only considering one transaction
• Adding profits incorrectly