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:

After you try — Pattern Transfer

Pattern: ONE-PASS RUNNING MINIMUM (single-transaction Stock I).

Template: minP = ∞, ans = 0; for each price p: minP = min(minP, p); ans = max(ans, p − minP).

When NOT (stock family):

Unlimited transactions → sum of all positive adjacent diffs (Stock II).
At most k transactions → DP states.
Data is a time series, not sorted for converging two-pointers pair discard — TP on unsorted prices is wrong.

Constraints with n up to 1e5 forbid the O(n²) “try every buy/sell pair” approach.

Edges

[1] → 0 (cannot sell on a later day).
[2,1] → 0; [1,2] → 1; all equal → 0.
Strictly decreasing → 0 (already in examples).

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

1. Why / judgment

Single-transaction max profit is not two-pointers on unsorted prices. It is a causal running minimum: sell day j can only pair with a buy day i<j, so track min price seen so far and max of p−minP. Brute O(n²) pairs fail at n=1e5; one pass is forced by constraints.

2. Worked example + complexity (K11)

prices = [3,2,6,5,0,3]
minP=∞, ans=0
p=3 → minP=3, ans=max(0,0)=0
p=2 → minP=2, ans=0
p=6 → minP=2, ans=max(0,4)=4
p=5 → minP=2, ans=max(4,3)=4
p=0 → minP=0, ans=4
p=3 → minP=0, ans=max(4,3)=4  → answer 4

Time: one loop, O(1) work → Θ(n)
Space: two scalars → Θ(1)
Brute pairs: n(n−1)/2 comparisons → Θ(n²) — rejects n=1e5 (~5·10^9).

3. Pattern — ONE-PASS RUNNING MINIMUM (K12)

Name: Stock I / max gain with one buy–sell.

Recognition: at most one transaction; buy before sell; maximize p_j − p_i for i<j.

When-NOT: unlimited transactions → sum positive adjacent diffs (Stock II); at most k → DP states; cooldown/fee → state machine DP; do not sort prices (destroys day order); do not two-pointer converge on unsorted series.

4. Edge hand-run (K13)

[1] → cannot sell later → 0
[2,1] → min then lower; never positive → 0
[1,2] → ans=1
[5,5,5] → 0
[8,6,5,2,1] → strict decrease → 0 (matches page example)

5. Interviewer follow-ups

Q1. Why not sort then take max−min?
A: Order is time; buy must precede sell. Sort loses chronology.

Q2. Complexity if try every pair?
A: Θ(n²) time — too slow for n=1e5.

Q3. How does Stock II differ?
A: Unlimited non-overlapping trades → sum all uphill segments, not one global max climb.

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

Pattern Transfer — ONE-PASS RUNNING MINIMUM (Stock I)

Pattern name: running minimum; max profit of a single buy-then-sell.

Recognition signals: buy once then sell once; buy index < sell index; maximize sell − buy.

Template:

minP = +∞
ans = 0
for p in prices:
  minP = min(minP, p)
  ans = max(ans, p - minP)
return ans

Why correct: at each candidate sell day, the optimal buy is the minimum price on any earlier day — exactly what minP tracks.

When NOT (stock family):

Unlimited transactions → sum max(prices[i]−prices[i−1], 0). Example: on [3,2,6,5,0,3] unlimited = (6−2)+(3−0)=7, not Stock-I’s 4.
k transactions / cooldown / fee → DP state machines.
Not converging two-pointers: prices are chronological, not sorted for pair discard; moving L/R does not preserve buy-before-sell optimality.

Brute: all pairs i < j → Θ(n²). One pass → Θ(n) time, O(1) space.

Edge hand-runs

[1]: minP=1, maxProfit=max(0,0)=0.
[5,5,5] → 0.
[2,1] → 0.
Main: [3,2,6,5,0,3] → min path reaches 2 then profit 4 at 6; later min 0 with profit 3 < 4 → answer 4.

Drill: Interviewer asks Stock II on the same array — what changes in one sentence?

🧩 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

← Problem 1 Running Sum of 1d Array Problem 2 Contains Duplicate →