Best Time to Buy and Sell Stock — Brute Force, Single-Pass Insight, and the Interview Script

A admin · Jun 21, 2026 · 5 views

Two Sum taught us to trade space for time using a HashMap. Today’s problem teaches the opposite lesson — sometimes you don’t need extra space at all, you just need to remember the right one thing as you walk through the data. Best Time to Buy and Sell Stock is the second most-asked easy problem in coding interviews at Google, Amazon, Flipkart, Swiggy, and Razorpay. It looks simple. It traps people who skip the brute force conversation. Let’s walk through it the way an interviewer wants to hear it.

The Problem

You’re given an array prices where prices[i] is the price of a stock on day i. You can buy once and sell once. Return the maximum profit. If no profit is possible, return 0.

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5

Why?
Day :  0  1  2  3  4  5
Price: 7  1  5  3  6  4

Buy on day 1 (price = 1)
Sell on day 4 (price = 6)
Profit = 6 - 1 = 5

That's the best we can do.

Another example — what if prices only go down?

Input:  prices = [7, 6, 4, 3, 1]
Output: 0

No matter which day we buy, every later day is cheaper.
We never sell, profit = 0.

Two clarifying questions you should ask the interviewer before writing anything:

“Can I sell on the same day I buy?” — Usually no. Sell must be on a later day.
“Is the answer 0 if no profit is possible, or should I return something else?” — Usually 0. Confirm.

Asking these wins you points before you’ve written a single line.

Step 1 — Brute Force First (Always)

Just like with Two Sum, do not jump to the optimal answer. Open with:

“Let me start with brute force. I’ll check every possible buy day against every possible sell day after it, track the maximum profit, and then we can talk about optimisation.”

The idea: for each day i, try selling on every later day j and remember the best profit we’ve seen.

prices = [7, 1, 5, 3, 6, 4]

Buy day 0 (7):  sell day 1 → -6 ❌
                sell day 2 → -2 ❌
                sell day 3 → -4 ❌
                sell day 4 → -1 ❌
                sell day 5 → -3 ❌
                best so far = 0

Buy day 1 (1):  sell day 2 →  4
                sell day 3 →  2
                sell day 4 →  5  ✅ new best
                sell day 5 →  3
                best so far = 5

Buy day 2 (5):  sell day 3 → -2
                sell day 4 →  1
                sell day 5 → -1
                best so far still = 5

... and so on.

Final answer: 5

Brute force code

fun maxProfit(prices: IntArray): Int {
    var maxProfit = 0
    // Start at 0 — if no profitable trade exists, this is what we return

    for (i in prices.indices) {
        for (j in i + 1 until prices.size) {
            // j starts at i+1 — we can only sell AFTER we buy
            val profit = prices[j] - prices[i]
            if (profit > maxProfit) {
                maxProfit = profit
            }
        }
    }
    return maxProfit
}

Complexity of brute force

Time   : O(n²)
            Outer loop — every possible buy day
            Inner loop — every possible sell day after it

Space  : O(1)
            We're just tracking one number (maxProfit)

This works. It gets the right answer. But on a 10,000-element array, it does about 50 million comparisons. The interviewer is going to ask for better.

Step 2 — The Interviewer Asks “Can You Do Better?”

Here’s the line that earns you the optimisation:

“The brute force is repeating work. For every sell day, I’m re-scanning the past to find the lowest buy price. But I could just remember the lowest price I’ve seen so far as I walk through the array once. Then at each day, the best profit for selling today is just todayPrice - lowestSoFar. That makes it a single pass.”

You’ve just described the optimal solution in plain English. Now write it.

Step 3 — The Single-Pass Insight

The whole optimisation rests on one observation:

If I’m selling today, I want to have bought at the cheapest price I’ve seen up to today.

That’s it. As we walk the array left to right, we keep track of two things:

minPrice — the cheapest price seen so far
maxProfit — the best profit we could’ve made if we sold on any day so far

At each new day, we ask two questions: “Could I make a better profit by selling today?” and then “Is today a new cheapest day to remember for the future?”

Full trace — prices = [7, 1, 5, 3, 6, 4]

Start:
   minPrice  = Int.MAX_VALUE
   maxProfit = 0

──────────────────────────────────────────────
Day 0, price = 7
   profit-if-sell-today = 7 - MAX_VALUE = very negative
   maxProfit stays at 0
   7 < MAX_VALUE? Yes → minPrice = 7
   State: minPrice = 7,  maxProfit = 0

──────────────────────────────────────────────
Day 1, price = 1
   profit-if-sell-today = 1 - 7 = -6
   maxProfit stays at 0  (we wouldn't sell at a loss)
   1 < 7? Yes → minPrice = 1   (new cheapest!)
   State: minPrice = 1,  maxProfit = 0

──────────────────────────────────────────────
Day 2, price = 5
   profit-if-sell-today = 5 - 1 = 4
   4 > 0? Yes → maxProfit = 4
   5 < 1? No → minPrice stays at 1
   State: minPrice = 1,  maxProfit = 4

──────────────────────────────────────────────
Day 3, price = 3
   profit-if-sell-today = 3 - 1 = 2
   2 > 4? No → maxProfit stays at 4
   3 < 1? No → minPrice stays at 1
   State: minPrice = 1,  maxProfit = 4

──────────────────────────────────────────────
Day 4, price = 6
   profit-if-sell-today = 6 - 1 = 5
   5 > 4? Yes → maxProfit = 5   ✅ new best
   6 < 1? No
   State: minPrice = 1,  maxProfit = 5

──────────────────────────────────────────────
Day 5, price = 4
   profit-if-sell-today = 4 - 1 = 3
   3 > 5? No
   4 < 1? No
   State: minPrice = 1,  maxProfit = 5

──────────────────────────────────────────────
Return maxProfit = 5  ✅

Notice we never went back. We never re-scanned. One pass, two variables, done.

The optimal code

fun maxProfit(prices: IntArray): Int {
    if (prices.isEmpty()) return 0
    // Guard against empty input — mention this in interviews

    var minPrice = Int.MAX_VALUE
    // Int.MAX_VALUE is a CONSTANT on Int — the largest possible Int
    // Starting at MAX_VALUE guarantees the first real price wins the comparison

    var maxProfit = 0

    for (price in prices) {
        // The order of these two lines matters — explained below
        if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice
        }
        if (price < minPrice) {
            minPrice = price
        }
    }
    return maxProfit
}

A Kotlin-idiomatic version (mention only if asked)

fun maxProfit(prices: IntArray): Int {
    var minPrice = Int.MAX_VALUE
    var maxProfit = 0
    prices.forEach { price ->
        minPrice = minOf(minPrice, price)
        maxProfit = maxOf(maxProfit, price - minPrice)
    }
    return maxProfit
}
// minOf() and maxOf() are TOP-LEVEL FUNCTIONS from kotlin.math — pick the smaller/larger
// Cleaner, but in interviews stick with the explicit version — easier to reason about

The Subtle Bug — Order of the Two Checks

This is the question interviewers love to drop. Look at the optimal code closely:

// ✅ CORRECT order:
if (price - minPrice > maxProfit) maxProfit = price - minPrice  // check profit FIRST
if (price < minPrice) minPrice = price                            // update minPrice AFTER

// ❌ WRONG order:
if (price < minPrice) minPrice = price                            // update minPrice FIRST
if (price - minPrice > maxProfit) maxProfit = price - minPrice  // BUG below

Why does the wrong order fail? Walk through day 1 with prices = [7, 1, 5, ...]:

Day 1, price = 1, state going in: minPrice = 7, maxProfit = 0

WRONG order:
   1 < 7?  Yes → minPrice = 1
   1 - 1 = 0 > 0? No → maxProfit stays at 0
   (OK for day 1 specifically, but...)

WRONG order, more dangerous case:
   Imagine price = 1 was the LAST day.
   You'd compute profit = 1 - 1 = 0 — "sell on the same day you bought."
   That violates the "buy then sell LATER" rule.

CORRECT order:
   Profit check uses the OLD minPrice (representing the cheapest price
   from a PREVIOUS day). Then we update minPrice for future iterations.
   This guarantees: profit is always computed using a buy day strictly
   before today.

Memorise this. When the interviewer asks “why this order?”, you have a confident answer: “to guarantee the buy day is strictly before the sell day.”

Complexity of the Optimal Solution

Time   : O(n)
            Single pass through the prices array.
            Each iteration does constant work — two comparisons.

Space  : O(1)
            Only two variables — minPrice and maxProfit.
            No HashMap, no extra array, no recursion stack.

This is one of the rare problems where the optimal solution is
BOTH faster AND uses less memory than the brute force. We dropped
from O(n²) time to O(n), and the space is still O(1).

Say this trade-off out loud during the interview:

“The brute force was O(n²) time, O(1) space. The optimal is O(n) time, O(1) space. We sped it up without paying any extra memory cost.”

Edge Cases to Mention

Bring these up before the interviewer does:

1. Empty array: prices = []
   → Return 0. Guard at the top of the function.

2. Single day: prices = [5]
   → Return 0. Can't sell without a buy day before it.

3. Strictly decreasing: prices = [7, 6, 4, 3, 1]
   → Return 0. No profitable trade exists.

4. Strictly increasing: prices = [1, 2, 3, 4, 5]
   → Buy day 0, sell day 4. Profit = 4.

5. All same price: prices = [5, 5, 5, 5]
   → Return 0. Profit is 0 every day, never updates from initial 0.

6. Two elements with profit: prices = [1, 100]
   → Buy day 0, sell day 1. Profit = 99.

7. Two elements without profit: prices = [100, 1]
   → Return 0.

The Conversation an Interviewer Wants to Hear

You: "Just to confirm — I can only buy once and sell once, and
      sell has to be on a strictly later day than buy?"
INT: "Yes."

You: "If no profit is possible, I return 0?"
INT: "Correct."

You: "Brute force first — for each possible buy day, I'll check every
      possible sell day after it and track the maximum profit."
     [write brute force]
     "That's O(n²) time, O(1) space."

INT: "Can you do better?"

You: "Yes. The brute force re-scans the past for the cheapest buy
      price at every sell day. I can avoid that by tracking the
      cheapest price I've seen as I walk the array once. At each
      day, the best profit ending today is todayPrice minus that
      running minimum."
     [write optimal solution]
     "O(n) time, O(1) space — faster AND no extra memory."

INT: "Why do you check the profit before updating minPrice?"

You: "To guarantee the buy day is strictly before the sell day.
      If I updated minPrice first, on a day with a new minimum, I'd
      compute a profit of zero by buying and selling on the same day.
      Checking profit first uses the OLD minPrice — the cheapest
      price from a previous day."

INT: "What if all prices are decreasing?"

You: "maxProfit stays at zero throughout, which is what we return.
      Same for an empty array — I guard against that at the top."

INT: "Could you solve this with a different approach? Maybe dynamic
      programming?"

You: "Yes — this is actually a one-state DP problem in disguise.
      The state at day i is the maximum profit ending at day i, and
      the recurrence is dp[i] = max(dp[i-1], prices[i] - minSoFar).
      But since we only need the answer, not the table, we can collapse
      the DP into two variables. That's exactly the solution we wrote."

That last answer is a senior signal. You’ve named the underlying pattern and explained why your simpler solution is equivalent.

Common Follow-Up Questions

Q1. What if I’m allowed multiple buys and sells?

This is “Best Time to Buy and Sell Stock II” — a separate, harder problem. The greedy solution there: sum up every positive day-to-day change. prices = [1, 2, 3, 4] gives profit (2-1) + (3-2) + (4-3) = 3. Mention you know it exists but don’t solve it unless asked.

Q2. What if there’s a cooldown after selling?

That’s “Best Time to Buy and Sell Stock with Cooldown” — a real DP problem with three states (holding, selling, cooling down). Significantly harder. Recognising the family is enough at this level.

Q3. Why not sort the array?

Sorting destroys the time order. We need to know which day came before which — you can’t sell before you buy. Sorting is wrong for this problem the same way it’s wrong for Two Sum.

Q4. What if prices can be negative?

The algorithm still works mathematically — price - minPrice just becomes a difference of two possibly-negative numbers. Real stock prices aren’t negative, but you can mention the code handles it cleanly without changes.

Q5. Can you do this in a stream — one number at a time, without an array?

Yes, and this is a good senior question. The algorithm naturally supports streaming because we only need two variables. Process each incoming price, update minPrice and maxProfit, throw the price away. Total memory: O(1) regardless of how long the stream is.

Quick Reference

BRUTE FORCE
───────────
- Idea       : Check every (buy day, sell day) pair
- Time       : O(n²)
- Space      : O(1)
- When       : Opening move in an interview — never the final answer

OPTIMAL: SINGLE PASS + RUNNING MINIMUM
──────────────────────────────────────
- Idea       : Track minPrice and maxProfit in one pass
- Time       : O(n)
- Space      : O(1)
- Trick      : Check profit BEFORE updating minPrice
- Pattern    : Kadane-style single-pass DP collapsed to two variables

ANSWER ORDER IN AN INTERVIEW
────────────────────────────
1. Clarify (sell after buy? return 0 if no profit?)
2. Brute force + complexity
3. Name the bottleneck (re-scanning the past)
4. Optimal solution + complexity
5. Defend the order of the two checks
6. Edge cases (empty, single, decreasing, all-equal)
7. Mention DP/streaming if pushed

Wrap-Up

The lesson from Two Sum was: trade space for time using a HashMap. The lesson here is different and just as important: you don’t always need extra space — sometimes you just need to remember the right one thing as you walk through the data. That pattern — one pass, a running minimum (or maximum, or count), O(1) extra space — shows up in dozens of interview problems: Maximum Subarray, Container With Most Water, Trapping Rain Water (partially), and several DP problems where the answer collapses to a couple of running variables.

Get comfortable with the running-minimum mindset and you’ll start seeing it everywhere. The brute-force-then-optimise script you practised on Two Sum still applies — same opening, same interviewer rhythm, just a different insight at the optimisation step.

One down, many to go. Practice the script out loud. Solve it on paper without an IDE. Then bring it to the whiteboard and watch the round move faster than the people who jumped straight to the answer.

Happy coding!

5 views · 0 comments

Comments (0)

No comments yet. Be the first to share your thoughts.