Buy and Sell Stocks All Variants in DSA Java

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.

Analogy: Imagine you have a fruit stand and prices change daily. You want to buy fruit cheap and sell it high to earn money. Sometimes you can only buy and sell once, sometimes many times, and sometimes you have to wait a day before buying again.

Prices: [7, 1, 5, 3, 6, 4]
Buy low ↑ at 1, sell high ↑ at 6
Profit = 6 - 1 = 5

Dry Run Walkthrough

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

Goal: Find max profit with at most 2 buy-sell transactions

Step 1: Start first transaction: buy at price 1 (lowest so far)

Day 0: price=7
Day 1: buy=1 ↑
Profit=0

Why: We want to buy at the lowest price to maximize profit later

Step 2: Sell first transaction at price 5

Day 2: sell=5 ↑
Profit=5 - 1 = 4

Why: Selling at 5 after buying at 1 gives profit 4

Step 3: Start second transaction: buy at price 3

Day 3: buy=3 ↑
Profit=4 (from first transaction)

Why: We can buy again to try to increase total profit

Step 4: Sell second transaction at price 6

Day 4: sell=6 ↑
Profit=4 + (6 - 3) = 7

Why: Selling at 6 after buying at 3 adds 3 more profit

Step 5: No more transactions allowed, end

Final profit = 7

Why: We reached max allowed transactions

Result:

Max profit with 2 transactions: 7

Annotated Code

DSA Java

public class BuySellStocks {

    // Function to find max profit with at most k transactions
    public static int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0 || k == 0) return 0;

        // If k >= n/2, we can do unlimited transactions
        if (k >= n / 2) {
            int maxProfit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    maxProfit += prices[i] - prices[i - 1];
                }
            }
            return maxProfit;
        }

        int[][] dp = new int[k + 1][n];

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

        return dp[k][n - 1];
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        int k = 2;
        int result = maxProfit(k, prices);
        System.out.println("Max profit with " + k + " transactions: " + result);
    }
}

if (k >= n / 2) { ... }

Handle unlimited transactions case by summing all positive price differences

for (int t = 1; t <= k; t++) { ... }

Iterate over number of transactions allowed

int maxDiff = -prices[0];

Track max difference of profit from previous transaction minus price to buy

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

Max profit on day d with t transactions is max of not selling today or selling today

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

Update maxDiff to consider buying at day d for next days

Output

Max profit with 2 transactions: 7

Complexity Analysis

Time: O(k * n) because we fill a dp table with k rows and n columns once

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

vs Alternative: Naive approach tries all buy-sell pairs repeatedly with O(n^2*k), this dp reduces it to O(k*n)

Edge Cases

Empty prices array

Returns 0 profit immediately

DSA Java

if (n == 0 || k == 0) return 0;

k is zero (no transactions allowed)

Returns 0 profit immediately

DSA Java

if (n == 0 || k == 0) return 0;

k >= n/2 (unlimited transactions)

Uses simple sum of all positive price differences for max profit

DSA Java

if (k >= n / 2) { ... }

When to Use This Pattern

When asked for max profit with limited or unlimited buy-sell transactions, use dynamic programming with states for transactions and days to optimize profit calculation.

Common Mistakes

Mistake: Trying to buy and sell multiple times without tracking transaction count properly
Fix: Use dp table indexed by transaction count and day to avoid invalid multiple transactions

Mistake: Not handling unlimited transactions case separately causing slow performance
Fix: Add early check for k >= n/2 and sum all positive differences directly

Summary

Calculates max profit from stock prices with constraints on number of buy-sell transactions.

Use when you need to maximize profit with limited or unlimited trades over time.

Track max profit per transaction count and day using dynamic programming to avoid repeated work.

Practice

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

easy

A. Minimize the number of transactions made

B. Find the day with the highest stock price

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 low and selling high on different days.

2. Step 2: Identify the correct objective

   Maximizing profit means choosing the best buy and sell days, not minimizing transactions or finding averages.

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 difference between buy and sell days [OK]

Common Mistakes:

• Confusing profit maximization with minimizing transactions
• Thinking the goal is to find highest price day only
• Ignoring the buy day before sell day order

2. Which of the following Java code snippets correctly initializes an array of stock prices for 5 days?

easy

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

B. int prices = [7, 1, 5, 3, 6];

C. int[] prices = (7, 1, 5, 3, 6);

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

Solution

1. Step 1: Check Java array initialization syntax

   Java arrays are initialized with curly braces {} and type declaration with [] after type.

2. Step 2: Validate each option

   Parentheses () are invalid, square brackets [] for values are invalid, missing braces {} and improper assignment are invalid. int[] prices = {7, 1, 5, 3, 6}; uses correct syntax.

3. Final Answer:

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

4. Quick Check:

   Correct array syntax = int[] prices = {7, 1, 5, 3, 6}; [OK]

Hint: Use curly braces {} for array values in Java [OK]

Common Mistakes:

• Using square brackets [] for values instead of curly braces
• Missing type[] before variable name
• Using parentheses () instead of braces

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

int[] prices = {7, 1, 5, 3, 6, 4};
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
    if (price < minPrice) minPrice = price;
    else if (price - minPrice > maxProfit) maxProfit = price - minPrice;
}
System.out.println(maxProfit);

medium

A. 5

B. 6

C. 4

D. 7

Solution

1. Step 1: Track minimum price and max profit during iteration

   Prices: 7,1,5,3,6,4. minPrice updates to 7 then 1. maxProfit updates when price - minPrice is greater.

2. Step 2: Calculate max profit step-by-step

   At price=5, profit=5-1=4; maxProfit=4. At price=6, profit=6-1=5; maxProfit=5. At price=4, profit=4-1=3; maxProfit stays 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Max profit = 6 - 1 = 5 [OK]

Hint: Track min price and update max profit on the fly [OK]

Common Mistakes:

• Confusing max profit with max price
• Not updating minPrice correctly
• Calculating profit without checking minPrice

4. Identify the error in this Java code snippet that attempts to calculate max profit with multiple transactions:

int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1])
        maxProfit += prices[i] - prices[i - 1];
    else
        i++;
}
System.out.println(maxProfit);

medium

A. Loop should start from i = 0

B. Missing initialization of maxProfit

C. Using prices[i] instead of prices[i-1] in calculation

D. Incorrect increment of loop variable inside else block

Solution

1. Step 1: Analyze loop increment and conditions

   The loop increments i each iteration, but inside else block it increments i again causing skipping elements.

2. Step 2: Identify why extra increment causes error

   Extra i++ skips days, missing some profit opportunities and causing incorrect result.

3. Final Answer:

   Incorrect increment of loop variable inside else block -> Option D

4. Quick Check:

   Loop variable increment only once per iteration [OK]

Hint: Avoid changing loop variable inside loop body [OK]

Common Mistakes:

• Incrementing loop variable twice causing skips
• Starting loop from wrong index
• Confusing price indices in calculation

5. Given an array of stock prices, how would you modify the algorithm to find the maximum profit with at most two transactions? Choose the best approach.

hard

A. Buy on the lowest price day and sell on the highest price day only.

B. Use two passes: first pass calculates max profit up to each day, second pass calculates max profit from each day to end, then combine.

C. Use a single pass and sum all positive differences between consecutive days.

D. Sort the prices array and pick the two largest differences.

Solution

1. Step 1: Understand the two transaction constraint

   At most two transactions means we can buy and sell twice, but transactions cannot overlap.

2. Step 2: Use two-pass approach for max profit calculation

   First pass calculates max profit from day 0 to i, second pass calculates max profit from i to end. Combining these gives max profit with two transactions.

3. Final Answer:

   Use two passes: first pass calculates max profit up to each day, second pass calculates max profit from each day to end, then combine. -> Option B

4. Quick Check:

   Two-pass method = Use two passes: first pass calculates max profit up to each day, second pass calculates max profit from each day to end, then combine. [OK]

Hint: Split problem into two single-transaction profits [OK]

Common Mistakes:

• Sorting prices loses day order information
• Summing all positive differences allows unlimited transactions
• Ignoring transaction count limit