Buy and Sell Stocks All Variants in DSA Rust

Mental Model

We want to find the best times to buy and sell stocks to maximize profit by looking at price changes over days.

Analogy: Imagine you are at a fruit market where prices change daily. You want to buy fruit at the lowest price and sell it later at a higher price to earn the most money.

Day:    0    1    2    3    4    5
Price: 100 -> 180 -> 260 -> 310 -> 40 -> 535
Buy at low price and sell at high price later.

Dry Run Walkthrough

Input: prices: [100, 180, 260, 310, 40, 535], max 2 transactions allowed

Goal: Maximize profit by buying and selling stocks at most twice

Step 1: Find max profit for first transaction from day 0 to day i

Day 0-5 profits: [0, 80, 160, 210, 210, 495]

Why: We track best profit if we sell on or before day i

Step 2: Find max profit for second transaction from day i to last day

Day 0-5 profits: [495, 495, 495, 495, 495, 0]

Why: We track best profit if we buy on or after day i

Step 3: Combine profits from first and second transactions for each day i

Combined profits: [495, 575, 655, 705, 705, 495]

Why: Sum profits to find max total profit with two transactions

Step 4: Choose max combined profit

Max profit = 705

Why: This is the best total profit achievable with two transactions

Result:

Max profit = 705

Annotated Code

DSA Rust

fn max_profit_two_transactions(prices: &[i32]) -> i32 {
    let n = prices.len();
    if n == 0 { return 0; }
    let mut profit_first = vec![0; n];
    let mut profit_second = vec![0; n + 1];

    // Calculate max profit for first transaction up to day i
    let mut min_price = prices[0];
    for i in 1..n {
        if prices[i] < min_price {
            min_price = prices[i];
        }
        profit_first[i] = profit_first[i - 1].max(prices[i] - min_price);
    }

    // Calculate max profit for second transaction from day i to end
    let mut max_price = prices[n - 1];
    for i in (0..n).rev() {
        if prices[i] > max_price {
            max_price = prices[i];
        }
        profit_second[i] = profit_second[i + 1].max(max_price - prices[i]);
    }

    // Combine profits to find max total profit
    let mut max_profit = 0;
    for i in 0..n {
        max_profit = max_profit.max(profit_first[i] + profit_second[i]);
    }
    max_profit
}

fn main() {
    let prices = vec![100, 180, 260, 310, 40, 535];
    let max_profit = max_profit_two_transactions(&prices);
    println!("Max profit = {}", max_profit);
}

let mut min_price = prices[0];

Initialize minimum price to track lowest buy price for first transaction

for i in 1..n { if prices[i] < min_price { min_price = prices[i]; } profit_first[i] = profit_first[i - 1].max(prices[i] - min_price); }

Update min price and max profit for first transaction up to day i

let mut max_price = prices[n - 1];

Initialize maximum price to track highest sell price for second transaction

for i in (0..n).rev() { if prices[i] > max_price { max_price = prices[i]; } profit_second[i] = profit_second[i + 1].max(max_price - prices[i]); }

Update max price and max profit for second transaction from day i to end

for i in 0..n { max_profit = max_profit.max(profit_first[i] + profit_second[i]); }

Combine profits from both transactions to find overall max profit

Output

Max profit = 705

Complexity Analysis

Time: O(n) because we scan the price list a few times linearly

Space: O(n) because we store profit arrays for each day

vs Alternative: Naive approach tries all buy/sell pairs with O(n^2) or O(n^3) time, which is much slower

Edge Cases

Empty price list

Returns 0 profit since no transactions possible

DSA Rust

if n == 0 { return 0; }

Prices always decreasing

Returns 0 profit since no profitable transactions

DSA Rust

profit_first[i] = profit_first[i - 1].max(prices[i] - min_price);

Only one day price

Returns 0 profit since cannot sell after buying

DSA Rust

if n == 0 { return 0; }

When to Use This Pattern

When asked to maximize stock profit with multiple transactions but limited count, use dynamic programming to track profits forward and backward.

Common Mistakes

Mistake: Trying to find max profit by only one pass without considering two transactions separately
Fix: Use two passes: one forward for first transaction and one backward for second transaction, then combine

Summary

Find max profit from at most two buy-sell transactions on stock prices.

Use when you can buy and sell stocks multiple times but with a limited number of transactions.

Split problem into two parts: max profit before day i and max profit after day i, then combine.

Practice

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

easy

A. Maximize the profit by choosing the best days to buy and sell stocks

B. Minimize the number of transactions regardless of profit

C. Find the stock price on the last day

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

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

3. Final Answer:

   Maximize the profit by choosing the best days to buy and sell stocks -> Option A

4. Quick Check:

   Goal = Maximize profit [OK]

Hint: Focus on profit maximization, not just transactions [OK]

Common Mistakes:

• Confusing profit maximization with minimizing transactions
• Ignoring the buy before sell rule
• Thinking the goal is to find average price

2. Which of the following Rust code snippets correctly initializes a vector of stock prices for the Buy and Sell Stocks problem?

easy

A. let prices = {7, 1, 5, 3, 6, 4};

B. let prices = vec![7, 1, 5, 3, 6, 4];

C. let prices = (7, 1, 5, 3, 6, 4);

D. let prices = [7, 1, 5, 3, 6, 4];

Solution

1. Step 1: Identify Rust vector syntax

   In Rust, vectors are created using vec![...] macro.

2. Step 2: Check each option

   let prices = vec![7, 1, 5, 3, 6, 4]; uses vec![...], which is correct. let prices = [7, 1, 5, 3, 6, 4]; is an array, not a vector. let prices = (7, 1, 5, 3, 6, 4); is a tuple. let prices = {7, 1, 5, 3, 6, 4}; is invalid syntax.

3. Final Answer:

   let prices = vec![7, 1, 5, 3, 6, 4]; -> Option B

4. Quick Check:

   Vector = vec![...] syntax [OK]

Hint: Use vec![] to create vectors in Rust [OK]

Common Mistakes:

• Using array syntax instead of vector
• Using tuple instead of vector
• Invalid curly braces for initialization

3. What is the output of the following Rust code that solves the 'Best Time to Buy and Sell Stock I' problem?

fn max_profit(prices: Vec<i32>) -> i32 {
    let mut min_price = i32::MAX;
    let mut max_profit = 0;
    for price in prices {
        if price < min_price {
            min_price = price;
        } else if price - min_price > max_profit {
            max_profit = price - min_price;
        }
    }
    max_profit
}

fn main() {
    let prices = vec![7, 1, 5, 3, 6, 4];
    println!("{}", max_profit(prices));
}

medium

A. 7

B. 6

C. 4

D. 5

Solution

1. Step 1: Trace the loop to find min_price and max_profit

   Start with min_price = MAX, max_profit = 0. Prices: 7,1,5,3,6,4 - price=7: min_price=7, max_profit=0 - price=1: min_price=1, max_profit=0 - price=5: profit=5-1=4 > 0, max_profit=4 - price=3: profit=3-1=2 < 4, max_profit=4 - price=6: profit=6-1=5 > 4, max_profit=5 - price=4: profit=4-1=3 < 5, max_profit=5

2. Step 2: Return max_profit

   max_profit is 5 after loop ends.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Max profit = 5 [OK]

Hint: Track min price and update max profit on each day [OK]

Common Mistakes:

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

4. Identify the bug in this Rust function intended to solve the 'Best Time to Buy and Sell Stock II' (multiple transactions allowed):

fn max_profit(prices: Vec<i32>) -> i32 {
    let mut profit = 0;
    for i in 0..prices.len() {
        if prices[i] > prices[i - 1] {
            profit += prices[i] - prices[i - 1];
        }
    }
    profit
}

medium

A. Index out of bounds error when i = 0

B. Profit calculation is incorrect for multiple transactions

C. Loop should start from 1 instead of 0

D. Prices vector should be mutable

Solution

1. Step 1: Analyze loop 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 bounds.

2. Step 2: Identify fix

   Loop should start from i=1 to avoid negative index access.

3. Final Answer:

   Index out of bounds error when i = 0 -> Option A

4. Quick Check:

   Negative index access causes runtime error [OK]

Hint: Start loop from 1 to avoid negative index [OK]

Common Mistakes:

• Starting loop at 0 causing invalid index
• Not checking vector length before access
• Assuming negative indices are valid

5. Given the stock prices [3, 3, 5, 0, 0, 3, 1, 4], what is the maximum profit achievable with at most two transactions (buy-sell pairs)?

hard

A. 5

B. 7

C. 6

D. 8

Solution

1. Step 1: Understand two transactions limit

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

2. Step 2: Find best two transactions

   Prices: 3,3,5,0,0,3,1,4 - First transaction: buy at 3 (day 0), sell at 5 (day 2), profit = 2 - Second transaction: buy at 0 (day 3), sell at 4 (day 7), profit = 4 Total profit = 2 + 4 = 6

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Sum of two best profits = 6 [OK]

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

Common Mistakes:

• Counting overlapping transactions
• Choosing wrong buy/sell days
• Ignoring the two transactions limit