easy Best Time to Buy and Sell

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Examples

- Input: [3, 2, 6, 5, 0, 3]
- Expected Output: 4
- Justification: Buy the stock on day 2 (price = 2) and sell it on day 3 (price = 6). Profit = 6 - 2 = 4.
- Input: [8, 6, 5, 2, 1]
- Expected Output: 0

Justification: Prices are continuously dropping, so no profit can be made.

- Input: [1, 2]
- Expected Output: 1
- Justification: Buy on day 1 (price = 1) and sell on day 2 (price = 2). Profit = 2 - 1 = 1.

Constraints:

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁴

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Best Time to Buy and Sell Stock (easy)

1. Why / judgment

Single transaction: max of prices[j]-prices[i] for iminimum price so far; at each day compute profit if sold today; track max. When-NOT: multiple transactions -> peak-valley / DP state machine (II/III/IV).

2. Big-O derivation (K11)

One pass: n updates of minPrice and maxProfit -> O(n) time, O(1) space.
Brute pairs O(n^2) fails at n=1e5.
Empty/single day -> 0. Descending prices -> profit 0.

3. Pattern + when-NOT (K12)

Name: RUNNING MIN + MAX DIFF (ONE TRANSACTION)

Recognition: buy once sell once later; max profit or 0.

When-NOT: Unlimited transactions -> sum positive adjacent diffs. k transactions -> DP hold/sold states. Fees/cooldown -> extra state transitions.

4. Edge hand-run (K13)

[7,1,5,3,6,4] -> buy1 sell6 =5
[7,6,4,3,1] -> 0
[2,4,1] -> 2 (buy2 sell4)

5. Interviewer follow-ups (model answers)

Q1. Why not global min and global max?
A: Max may occur before min — must respect time order i<j.

Q2. Is Kadane related?
A: Yes: on daily diffs, max subarray sum equals max one-transaction profit.

Q3. Space O(1) enough?
A: Yes — only minSoFar and ans.

6. Short drills

Drill: [3,3,3]->0
Drill: [1,2]->1
Drill: map to Kadane on diffs.

✅ Solution Best Time to Buy and Sell Stock

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Examples

- Input: [3, 2, 6, 5, 0, 3]
- Expected Output: 4
- Justification: Buy the stock on day 2 (price = 2) and sell it on day 3 (price = 6). Profit = 6 - 2 = 4.
- Input: [8, 6, 5, 2, 1]
- Expected Output: 0

Justification: Prices are continuously dropping, so no profit can be made.

- Input: [1, 2]
- Expected Output: 1
- Justification: Buy on day 1 (price = 1) and sell on day 2 (price = 2). Profit = 2 - 1 = 1.

Constraints:

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁴

Solution

To solve this problem, we iterate through the list of stock prices to find the maximum profit that can be made by buying and selling once. The approach involves keeping track of the lowest price seen so far and calculating the potential profit if the stock were sold at the current price. As we continue to iterate through the prices, we consistently update the minimum price and the maximum profit observed. By the end of the loop, we have determined the highest possible profit that can be achieved from a single buy-sell transaction, ensuring an efficient solution with linear time complexity.

Step-by-Step Algorithm

Initialize Variables:
- Set a variable to hold the minimum price encountered so far to a very high value (initially, the maximum possible integer value).
- Set a variable to hold the maximum profit calculated so far to 0.
Iterate Through Each Price in the Array:
- For each price in the given array:
  - Update the Minimum Price:
    - Compare the current price with the minimum price encountered so far.
    - If the current price is lower, update the minimum price to the current price.
  - Calculate the Potential Profit:
    - Subtract the updated minimum price from the current price to calculate the potential profit if selling at this price.
  - Update the Maximum Profit:
    - Compare the calculated potential profit with the maximum profit recorded so far.
    - If the potential profit is higher, update the maximum profit to this value.
Return the Maximum Profit:
- After completing the iteration through all prices, return the maximum profit calculated.

Algorithm Walkthrough

Consider the input [3, 2, 6, 5, 0, 3]:

Initialize minPrice as infinity and maxProfit as 0.
Iterate through the list:
- Day 1: price is 3
  - minPrice is updated to 3.
  - Profit = 3 - 3 = 0. maxProfit remains 0.
- Day 2: price is 2
  - minPrice is updated to 2.
  - Profit = 2 - 2 = 0. maxProfit remains 0.
- Day 3: price is 6
  - minPrice remains 2.
  - Profit = 6 - 2 = 4. maxProfit is updated to 4.
- Day 4: price is 5
  - minPrice remains 2.
  - Profit = 5 - 2 = 3. maxProfit remains 4.
- Day 5: price is 0
  - minPrice is updated to 0.
  - Profit = 0 - 0 = 0. maxProfit remains 4.
- Day 6: price is 3
  - minPrice remains 0.
  - Profit = 3 - 0 = 3. maxProfit remains 4.
The final maxProfit is 4.

Code

java

public class Solution {

  public int maxProfit(int[] prices) {
    // Initialize minPrice to the maximum possible integer value
    int minPrice = Integer.MAX_VALUE;
    // Initialize maxProfit to 0
    int maxProfit = 0;
    // Iterate through each price in the prices array
    for (int price : prices) {
      // Update minPrice to be the minimum of minPrice and the current price
      minPrice = Math.min(minPrice, price);
      // Update maxProfit to be the maximum of maxProfit and the difference between the current price and minPrice
      maxProfit = Math.max(maxProfit, price - minPrice);
    }
    // Return the final maxProfit
    return maxProfit;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] example1 = { 3, 2, 6, 5, 0, 3 };
    int[] example2 = { 8, 6, 5, 2, 1 };
    int[] example3 = { 1, 2 };
    System.out.println(solution.maxProfit(example1)); // Output: 4
    System.out.println(solution.maxProfit(example2)); // Output: 0
    System.out.println(solution.maxProfit(example3)); // Output: 1
  }
}

Complexity Analysis

Time Complexity: O(n), where n is the number of days. This is because the algorithm iterates through the list of prices once, performing constant-time operations for each price.
Space Complexity: O(1), as it uses a constant amount of extra space (two variables to keep track of minPrice and maxProfit).

🎯 STRICT STANDOUT — Solution Best Time to Buy and Sell Stock

1. Why / judgment

Implement running min: init min=prices[0], profit=0; for each price update profit with price-min and min with price. Correct because any optimal sell day j pairs with the minimal buy in [0..j]. Hand-run [7,1,5,3,6,4]: min drops to 1; max profit 5 at 6.

2. Big-O derivation (K11)

O(n)/O(1).
Trace: p=7 min7 pr0; p1 min1; p5 pr4; p3; p6 pr5; p4 -> ans5.
[2,4,1]: max is 2 not 0 after seeing 1.

3. Pattern + when-NOT (K12)

Name: ONE-PASS MIN TRACKING

Recognition: single transaction max profit.

When-NOT: Multiple sells -> other stock problems. Need buy/sell day indices -> keep argmin with profit updates.

4. Edge hand-run (K13)

n=1 -> 0
peak then valley: only pre-peak window matters
equal prices -> 0

5. Interviewer follow-ups (model answers)

Q1. Invariant of minSoFar?
A: After processing prefix i, min is min of prices[0..i] and profit is best sell <=i.

Q2. Kadane on diffs proof sketch?
A: profit of buy at i sell j = sum diffs i+1..j; max subarray sum of diffs.

Q3. Overflow?
A: prices fit int; profit >=0 <= max price.

6. Short drills

Drill: [1,2,3,4]->3
Drill: [4,3,2,1]->0
Drill: code with indices of buy/sell.

🧩 Pattern · Arrays

Recognize it: Scan once tracking what you need (running max/sum), or precompute a prefix-sum / hash → turn O(n²) into O(n).

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Best Time to Buy and Sell? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Best Time to Buy and Sell** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Best Time to Buy and Sell** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Best Time to Buy and Sell**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Best Time to Buy and Sell**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Plus One Find the Difference of Two Arrays →