Best Time to Buy and Sell Stock in Java DSA: From Brute Force to a Single Clean Pass

Solve Best Time to Buy and Sell Stock in Java DSA, from a brute-force pair check to a clean one-pass running-minimum trick, with full step-by-step dry runs.

1. Introduction

Best Time to Buy and Sell Stock in Java is one of those problems that looks tricky but hides a very simple idea. You get a list of daily prices. Your job is to buy on one day and sell on a later day for the biggest profit.

There is one rule you cannot break. You must buy before you sell. So you can never sell on a day that comes earlier than your buy day.

If no profit is possible, the answer is just 0. That happens when prices only fall. In that case, it is smarter to not trade at all.

We will solve this in two steps, like we always do. First comes brute force, which checks every buy and sell pair. Then comes a clean one-pass trick that walks the array once and remembers the cheapest day so far.

Every approach gets a full, step-by-step dry run on the same six prices. Nothing is skipped, so you can watch exactly what each line does and what changes at every step.

2. Understanding the Problem

Let us pin down the rules before we touch any code.

• You get an array of prices, like [7, 1, 5, 3, 6, 4]. Each slot is the price on one day.
• Pick one day to buy and a later day to sell.
• Profit is the sell price minus the buy price.
• Return the largest profit you can get. If every choice loses money, return 0.

For our array the answer is 5. You buy at 1 on day 1 and sell at 6 on day 4. No other pair beats that gap.

Notice the lowest price, 1, does not sit at the start. And the highest price, 7, sits on day 0 where you cannot use it. That gap between order and value is the whole challenge here.

3. Concepts You Need Here

3.1 Buy Low, Sell High, In Order

The profit rule is simple: sell price minus buy price. But the buy day must come first. So a big price early on is useless if nothing cheaper comes before it.

3.2 Track the Cheapest Day So Far

Here is the key trick. As you walk left to right, keep the lowest price you have seen up to now. On each new day, pretend you sell today and buy on that cheapest earlier day.

• The cheapest day always sits before today, so the buy-before-sell rule holds automatically.
• You only need one number in memory, not the whole history.

4. Approach 1: Brute Force

Try every buy day paired with every later sell day. Keep the biggest profit you find. It is slow, but it proves you understand the goal.

4.1 Pseudocode

best = 0
 
for buy from 0 to n-1:            // buy day
    for sell from buy+1 to n-1:  // a later sell day
        profit = prices[sell] - prices[buy]
        if profit > best:
            best = profit
 
return best

4.2 Pseudocode Explained

• The outer loop picks a buy day.
• The inner loop tries every day after it as the sell day.
• For each pair we work out the profit and keep it only if it beats the best so far.
• Starting best at 0 handles the case where no trade makes money.

4.3 Java Code

public class StockBrute {
 
    public static int maxProfit(int[] prices) {
        int best = 0;
        for (int buy = 0; buy < prices.length; buy++) {
            for (int sell = buy + 1; sell < prices.length; sell++) {
                int profit = prices[sell] - prices[buy];
                if (profit > best) {
                    best = profit;
                }
            }
        }
        return best;
    }
 
    public static void main(String[] args) {
        int[] prices = { 7, 1, 5, 3, 6, 4 };
        System.out.println(maxProfit(prices)); // 5
    }
}

4.4 Java Code Explained

• Line 4 starts best at 0, our safety net for a no-profit case.
• Then line 5 picks the buy day, and line 6 picks a later sell day.
• Next, line 7 finds the profit for that pair.
• Lines 8 to 10 save it only when it beats the current best.

4.5 Dry Run of the Brute Force

Array: [7, 1, 5, 3, 6, 4]. The two loops try every valid buy and sell pair, in order. We trace all 15 of them, so nothing is hidden. Watch the best column climb.

4.6 Reading the Dry Run

Let us walk the whole trace, group by group, and see what the loops are doing.

Steps 1 to 5: buy day is 0, price 7.

The outer loop parks the buy on day 0, where the price is 7. That is the most expensive day, so no sell day can turn a profit.

• Step 1: sell on day 1 at price 1. Profit is 1 – 7 = -6, a big loss.
• Steps 2 to 4: sell on days 2, 3, and 4. Profits are -2, -4, -1, all still below zero.
• Then step 5 sells on day 5 at 4, giving -3. Every pair here loses money.

So best stays at 0 through this whole group. Buying at the peak was doomed from the start.

Steps 6 to 9: buy day is 1, price 1.

Now the buy sits on the cheapest day, price 1. This is where the real profits live.

• Step 6: sell on day 2 at 5. Profit is 5 – 1 = 4. That beats 0, so best jumps to 4.
• Step 7: sell on day 3 at 3. Profit is 2, which does not beat 4, so best holds.
• At step 8: sell on day 4 at 6. Profit is 6 – 1 = 5. A new record, so best rises to 5.
• Then step 9: sell on day 5 at 4. Profit is 3, below 5, so nothing changes.

This group found the winning trade at step 8. Buying low at 1 and selling high at 6 gives the top profit of 5.

Steps 10 to 15: buy days 2, 3, then 4.

From here the buy price is never that cheap again, so best cannot grow.

• Steps 10 to 12: buy at 5 on day 2. The best sell is 6, giving only 1, far under 5.
• Steps 13 and 14: buy at 3 on day 3. Selling at 6 gives 3, still short of 5.
• Finally step 15: buy at 6 on day 4, sell at 4. That loses 2, so best stays put.

Fifteen pairs were tested in all, yet the answer settled back at step 8. The brute force had to check the other seven pairs anyway, because it has no way to skip them.

4.7 Time and Space Cost

• Time is O(n²), because of the two nested loops.
• Space is O(1), since we only keep a single best value.

Fifteen pairs for six prices is fine. For a few thousand prices it crawls, which is why we improve it next.

5. Approach 2: One Pass With a Running Minimum

Drop the inner loop completely. Walk the prices once, from left to right. Keep the cheapest price seen so far, and on each day check the profit if you sell today. This is the answer interviewers hope to see.

5.1 Pseudocode

minPrice = a very large number
best = 0
 
for each price in prices:
    todayProfit = price - minPrice
    if todayProfit > best:
        best = todayProfit
    if price < minPrice:
        minPrice = price
 
return best

5.2 Pseudocode Explained

• minPrice remembers the cheapest buy day seen so far.
• todayProfit asks: what if I sell at today’s price using that cheapest buy?
• We keep todayProfit only when it beats the best so far.
• After the check, we update minPrice if today is even cheaper.

5.3 Java Code

public class StockOnePass {
 
    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int best = 0;
        for (int price : prices) {
            int todayProfit = price - minPrice;
            if (todayProfit > best) {
                best = todayProfit;
            }
            if (price < minPrice) {
                minPrice = price;
            }
        }
        return best;
    }
 
    public static void main(String[] args) {
        int[] prices = { 7, 1, 5, 3, 6, 4 };
        System.out.println(maxProfit(prices)); // 5
    }
}

5.4 Java Code Explained

• Line 4 starts minPrice sky-high, so the first real price always wins as the new minimum.
• Then line 6 walks each price once.
• Line 7 works out today’s profit against the cheapest buy so far.
• Lines 8 to 10 keep that profit only when it sets a new record.
• Lines 11 to 13 lower minPrice when today is the cheapest day yet.

5.5 Dry Run of the One-Pass Approach

Array: [7, 1, 5, 3, 6, 4]. We trace every single day. The order matters: we check the profit first, then update minPrice. So minPrice shown is the value used for today’s profit, before any update.

Legend: minPrice before is the cheapest price seen on earlier days, used as the buy price for today. todayProfit is what you would earn selling at today’s price. best is the top profit found so far.

5.6 Reading the Dry Run

Let us go day by day and watch the two values move.

Day 0, price 7.

minPrice still holds its huge starting value, so there is no real buy day yet.

• todayProfit would be a strange giant negative, so it never beats best. best stays 0.
• Then 7 is smaller than the huge start, so minPrice drops to 7. Now day 0 is our cheapest buy.

Day 1, price 1.

We first check profit against the current minPrice, which is 7.

• todayProfit is 1 – 7 = -6. That loses money, so best stays 0.
• Next, 1 is cheaper than 7, so minPrice falls to 1. This is the moment that unlocks all future profit.

Day 2, price 5.

Now minPrice is 1, the best buy day we have found.

• todayProfit is 5 – 1 = 4. That beats 0, so best rises to 4.
• Then 5 is not cheaper than 1, so minPrice stays at 1. We hold on to our cheap buy day.

Day 3, price 3.

• todayProfit is 3 – 1 = 2. That does not beat 4, so best holds at 4.
• Also 3 is not below 1, so minPrice stays at 1 again.

A dip in price does not hurt us. We simply skip it, because selling into a dip earns less.

Day 4, price 6.

This is the winning day, and minPrice is still 1.

• todayProfit is 6 – 1 = 5. A new record, so best climbs to 5.
• Then 6 is not below 1, so minPrice stays at 1.

Notice how the single stored minimum from day 1 pays off three days later. We never had to look back.

Day 5, price 4.

• todayProfit is 4 – 1 = 3. Below 5, so best stays 5.
• Finally 4 is not below 1, so minPrice stays at 1 and the walk ends.

One pass, two variables, and the answer is 5. The order of the two checks is what makes it correct. We measure today’s profit against an earlier buy first, then lower the minimum, so a price can never buy and sell on the same day.

5.7 Time and Space Cost

• Time is O(n), because we walk the array just once.
• Space is O(1), since we keep only minPrice and best.

This is as fast as it gets. You must read every price at least once, and this does exactly that, no more.

6. The Dry Run on Paper

Tables are exact, but a sketch often lands faster. Here is the same one-pass trace drawn by hand.

• A green row marks each day where best grows to a new record.
• The min so far column shows the cheapest buy locking in at 1 on day 1.
• At the bottom, the finished answer reads 5, from buying at 1 and selling at 6.

7. Comparing the Two Approaches

Both give the same answer. They just pay very different prices.

The two share the same tiny memory cost. What splits them is time. The brute force rechecks pairs it could safely skip, while the one pass carries a single minimum and never looks back.

In an interview, start with brute force and name its wasted inner loop. Then tighten it into the one-pass sweep and explain the running minimum. That climb from slow to fast is the story interviewers want to hear.

8. Common Mistakes and Edge Cases

A few small traps catch beginners on this problem. Keep them in mind.

• Updating minPrice before checking today’s profit lets one day buy and sell itself, which inflates the answer.
• Returning a negative number is wrong. When prices only fall, the answer is 0, so start best at 0.
• Prices that keep dropping, like [7, 6, 4, 3, 1], should return 0, since no trade wins.
• A single price, like [5], has no later day to sell, so the answer is 0.
• An empty array should also return 0 and never crash.

Run those falling and single-price cases through your code before you call it done. They catch more bugs than any ordinary input will.

9. Interview Questions

10. Conclusion

Best Time to Buy and Sell Stock in Java looks like it needs two loops. But once you spot the running-minimum trick, it shrinks to a single clean pass.

Our six-price trace showed the payoff clearly. Brute force ground through all fifteen pairs. The one pass remembered the cheapest day and found the same profit of 5 in a single walk.

So take the pattern, not just the answer. When a problem asks for the best pair in order, ask what you can remember as you go. Often one stored value replaces a whole inner loop.

That habit turns a slow square of work into a quick straight line. It will do the same for many array problems waiting further down the list.

11. Further Reading

• LeetCode Best Time to Buy and Sell Stock problem — practice the original problem and submit your own solution.
• Oracle Java Arrays documentation — the official reference for array helpers used across this series.
• Previous in this series: Two Sum in Java — find the two numbers that add up to a target using a hash map.
• Next in this series: Contains Duplicate in Java — use a hash set to spot a repeated value in one pass.

javahandson.com | DSA Series | Arrays & Strings