Buy and Sell Stocks All Variants in DSA Java - 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 vary by constraints like the number of transactions allowed, cooldown periods, or transaction fees. Each variant asks how to optimize profit given these rules. They help understand dynamic programming and greedy strategies in real-world financial scenarios.

Why it matters

Without these concepts, people might make poor investment decisions or fail to write efficient algorithms for financial data analysis. These problems model real trading constraints and teach how to handle complex decision-making over time. They also build skills in optimization and dynamic programming, which apply broadly in software and data science.

Where it fits

Learners should know arrays, basic loops, and conditional logic before this. After mastering these variants, learners can explore advanced dynamic programming, greedy algorithms, and financial modeling techniques.

Mental Model

Core Idea

Maximize profit by choosing the best buy and sell days under given constraints using optimal subproblem solutions.

Think of it like...

It's like planning a road trip where you want to stop at gas stations to refuel cheaply and sell leftover fuel at high prices later, but with rules like limited stops or waiting times between stops.

Days:  1   2   3   4   5
Prices: 7 | 1 | 5 | 3 | 6
Buy on day 2 (price=1), sell on day 3 (price=5), profit=4
Constraints modify when/how often you can buy/sell.

Build-Up - 7 Steps

1

Foundation

Single Transaction Maximum Profit

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

Given an array of prices, find the maximum difference between a later sell price and an earlier buy price. Iterate once, track the minimum price so far and calculate potential profit at each step.

Result

For prices [7,1,5,3,6,4], max profit is 5 (buy at 1, sell at 6).

Understanding that tracking the minimum price so far allows a single pass solution is key to efficient profit calculation.

2

Foundation

Unlimited Transactions Profit

Concept: Calculate max profit when you can buy and sell multiple times without limits.

Sum all positive differences between consecutive days. This simulates buying before every price rise and selling at the peak.

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

Recognizing that every upward price movement can be exploited independently simplifies the problem.

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.

Split the array into two parts at each day. Calculate max profit from left and right separately, then combine. Use arrays to store max profit up to day i and from day i to end.

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

Knowing how to break the problem into two subproblems and combine results is a powerful dynamic programming technique.

4

Intermediate

K Transactions Limit

🤔Before reading on: do you think increasing K always increases profit linearly? Commit to yes or no.

Concept: Generalize to at most K transactions using dynamic programming with state tracking.

Use a 2D DP array where dp[t][d] is max profit up to day d with t transactions. Update by comparing no transaction vs selling today after buying on a previous day. Optimize inner loop with a variable tracking max of dp[t-1][m] - price[m].

Result

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

Understanding how to track states for multiple transactions and optimize nested loops is key for scalable solutions.

5

Intermediate

Cooldown Period Between Transactions

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

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

Use three states: hold (holding stock), sold (just sold), rest (cooldown or no stock). Update states each day based on previous states and prices. Max profit is max of sold or rest at the end.

Result

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

Modeling cooldown as separate states clarifies constraints and enables correct profit calculation.

6

Advanced

Transaction Fee Impact

🤔Before reading on: do you think paying a fee per transaction always reduces profit by fee amount? Commit to yes or no.

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

Modify the hold state update to subtract fee when buying. Use two states: hold and cash. Update hold as max of previous hold or cash minus price and fee. Update cash as max of previous cash or hold plus price.

Result

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

Accounting for fees changes when transactions are profitable, requiring careful state updates.

7

Expert

Optimizing Space and Time Complexity

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

Concept: Reduce space from O(K*N) to O(K) and optimize time by tracking max differences.

Use rolling arrays or variables to store only necessary previous states. For large K, if K > N/2, treat as unlimited transactions. This avoids unnecessary computation and memory use.

Result

For large inputs, solution runs efficiently with minimal memory.

Knowing when to simplify problem constraints and optimize DP storage is crucial for real-world performance.

Under the Hood

These problems use dynamic programming to store intermediate results of subproblems representing states like holding stock, sold stock, or resting. Transitions between states model buying, selling, cooldowns, and fees. The algorithm iterates over days and transactions, updating states based on previous values and prices to build up the maximum profit.

Why designed this way?

Dynamic programming was chosen because the problem has overlapping subproblems and optimal substructure. Early greedy approaches failed under constraints like cooldowns or fees. DP allows systematic exploration of all valid transaction sequences efficiently.

┌─────────────┐
│   Day Loop  │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Transaction │
│   States    │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Update hold │
│ and cash    │
│ states      │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Max Profit  │
│ Calculation │
└─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does buying at the lowest price always guarantee maximum profit? Commit to yes or no.

Common Belief: Buying at the lowest price always yields the highest profit.

Reality: Buying at the lowest price is not enough; you must also sell at the highest price after that day to maximize profit.

Why it matters: Ignoring the sell timing can lead to suboptimal profits or losses.

Quick: Can you always make profit if unlimited transactions are allowed? Commit to yes or no.

Common Belief: Unlimited transactions guarantee maximum profit regardless of price pattern.

Reality: If prices only fall or stay the same, no profit is possible even with unlimited transactions.

Why it matters: Assuming profit is always possible leads to incorrect algorithm assumptions and wasted computation.

Quick: Does adding a cooldown always reduce maximum profit? Commit to yes or no.

Common Belief: Cooldown periods always reduce the maximum achievable profit.

Reality: Cooldowns restrict transaction timing but sometimes force better timing, which can maintain or even increase profit in rare cases.

Why it matters: Misunderstanding cooldown effects can cause wrong algorithm design or missed optimization opportunities.

Quick: Does paying a transaction fee always reduce profit by the fee amount? Commit to yes or no.

Common Belief: Transaction fees simply subtract from total profit linearly.

Reality: Fees affect when transactions are profitable, sometimes making small trades unprofitable and changing optimal buy/sell days.

Why it matters: Ignoring fee impact on transaction timing leads to incorrect profit calculations.

Expert Zone

1

Tracking states separately for holding and not holding stock simplifies handling complex constraints like cooldowns and fees.

2

When K is large relative to days, treating the problem as unlimited transactions reduces complexity drastically.

3

Optimizing DP by maintaining max differences avoids nested loops, improving time from O(K*N^2) to O(K*N).

When NOT to use

These DP solutions are inefficient for extremely large datasets or streaming data where approximate or heuristic methods like sliding window or greedy algorithms may be better.

Production Patterns

In real trading systems, variants of these algorithms help in backtesting strategies, risk management, and automated trading bots that must consider transaction costs, cooldowns, and limited trades.

Connections

Dynamic Programming

Builds-on

Understanding buy/sell stock problems deepens grasp of DP state management and optimization techniques.

Financial Portfolio Optimization

Application

These algorithms model simplified trading constraints, foundational for complex portfolio management.

Operations Research

Similar pattern

Maximizing profit under constraints parallels resource allocation problems in operations research.

Common Pitfalls

#1 Trying to solve multiple transactions by greedily picking local profits without considering global constraints.

Wrong approach:

int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1]) {
profit += prices[i] - prices[i-1];
}
}
// Works only for unlimited transactions without constraints

Correct approach:

Use DP states to track transactions and constraints explicitly, not just sum positive differences.

Root cause:

Misunderstanding that constraints like cooldown or transaction limits invalidate simple greedy sums.

#2 Not handling edge cases like empty price arrays or single-day prices.

Wrong approach:

int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) return 0;
int minPrice = prices[0]; // safe after check
// ...
}

Correct approach:

Check if prices array is empty or has less than 2 elements before processing.

Root cause:

Assuming input always has valid data leads to runtime errors.

#3 Confusing transaction fee application timing, subtracting fee on sell instead of buy or vice versa.

Wrong approach:

hold = Math.max(hold, cash - price[i]); // missing fee
cash = Math.max(cash, hold + price[i] - fee);

Correct approach:

hold = Math.max(hold, cash - price[i] - fee);
cash = Math.max(cash, hold + price[i]);

Root cause:

Misunderstanding when fees apply changes state update logic.

Key Takeaways

Maximizing stock trading profit requires careful tracking of buy and sell decisions under given constraints.

Dynamic programming models states like holding or not holding stock to handle complex rules like cooldowns and fees.

Simple greedy solutions work only for unlimited transactions without constraints.

Optimizing DP with state compression and recognizing problem limits improves performance significantly.

Understanding these variants builds strong foundations for real-world financial algorithm design and optimization.

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