Loading…

mediumArraysSometimes asked

Minimum Loss

Q: How do you solve Minimum Loss using the Brute Force — All Ordered Pairs approach?

When to use it: State it first to fix the definition of a valid loss, then note the O(n²) blowup at n = 2×10⁵. The literal reading of the problem: a valid trade is a pair of years i price[j], and the loss is price[i] − price[j]. Enumerate every such pair and keep the smallest loss. **Why both conditions matter.** `i price[j]` enforces that it's a loss, not a gain. Drop either and you count illegal trades. **Use long throughout.** Prices reach 10¹⁶, so both the values and the differences must be 64-bit. A 32-bit int silently wraps. **Why we don't ship it.** With n up to 2×10⁵, n²/2 ≈ 2×10¹⁰ comparisons — far too slow. Sorting reveals that only a handful of candidate pairs ever matter. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Minimum Loss using the Sort by Price + Adjacent Scan (Optimal) approach?

When to use it: The answer they want: sort prices, keep years, and only consecutive sorted prices can be the minimum loss. Sort the prices ascending, carrying each price's original year. Now walk consecutive pairs. For a sorted pair `(lower, higher)`, the only way it's a valid trade is to **buy the higher price and sell the lower** — and that requires the higher price's year to be *earlier* than the lower price's year. If so, the candidate loss is `higher − lower`. **Why only adjacent pairs matter.** Suppose the optimal trade buys at price H and sells at price L with H > L. Take any other price X with L < X < H. If X's year is before L's year, then buying X and selling L is also valid and gives a *smaller* loss (X − L < H − L) — contradicting optimality. Otherwise X's year is after L's year; but X < H, and if X's year is after the buy year of H then selling X (instead of L) against H... the careful version of this argument shows the minimum loss is always realized by two prices with **no other price strictly between them** — i.e. consecutive in sorted order. So we never need non-adjacent pairs. **Why we keep the year.** Sorting by price throws away the time order, but the trade legality depends entirely on it. Storing `(price, year)` lets us check `year(higher) < year(lower)` in O(1) per pair. **Why long.** Prices reach 10¹⁶; the differences do too. Use 64-bit for the stored prices and the running best. **Streaming variant (TreeSet).** Equivalently, process prices in year order while maintaining an ordered set of prices seen in earlier years. For each new (sell) price, query the smallest stored price strictly greater than it (a higher, earlier buy) and take that difference. Same O(n log n), handy when prices arrive one at a time. Time complexity: O(n log n). Space complexity: O(n).

Arrays & Hashing · 76 of 83 · 9 min

Lauren has a chart of the price of a particular house over the years. Each year she could buy the house and, in some later year, sell it. She is only interested in transactions that result in a loss — selling for strictly less than she paid.

Given the prices indexed by year, find the minimum loss Lauren can incur. It is guaranteed that at least one losing transaction is possible, and all prices are distinct.

In plain English

We need two years i < j (i earlier) with price[i] > price[j], minimizing price[i] − price[j]. Brute force checks every ordered pair. The key observation: if we sort the prices, the smallest positive gap between a buy and a sell can only come from prices that are adjacent in sorted order — but we must keep each price's original year to verify the buy happened before the sell.

Examples

Example 1

Input: price = [20, 7, 8, 2, 5]
Output: 2
Note: Buy at 7 (year 2), sell at 5 (year 5): loss 2. That's the smallest loss among all buy-earlier/sell-later pairs.

Example 2

Input: price = [2, 3, 4, 1]
Output: 1
Note: Buy at 2 (year 1), sell at 1 (year 4): loss 1. Smaller than buying at 3 or 4 and selling the final 1.

Example 3

Input: price = [5, 10, 3]
Output: 2
Note: Buy at 5 (year 1), sell at 3 (year 3): loss 2. Buying at 10 (year 2) and selling 3 gives a larger loss of 7.

Constraints

1 ≤ n ≤ 2×10⁵
1 ≤ price[i] ≤ 10¹⁶
All prices are distinct
At least one valid (buy earlier, sell later at a loss) transaction exists

Clarifying questions4First question: Must the sale happen in a later year than the purchase?Explore questions

Q1.Must the sale happen in a later year than the purchase?
Yes. Buy at an earlier index, sell at a later index. The higher (buy) price must therefore have the smaller original index.
Q2.Is selling at a profit allowed?
No — only losing transactions count. We minimize a strictly positive loss, never a gain.
Q3.Are prices guaranteed distinct?
Yes. That makes sorting unambiguous and every adjacent difference strictly positive.
Q4.How large can prices get?
Up to 10¹⁶, which exceeds the 32-bit range. Use 64-bit integers for prices and the computed loss.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Lauren buys a house in one year and must sell it in a *later* year at a *loss* (sell price < buy price); minimize that loss. Pair each price with its year, sort by price, and look only at consecutive prices in sorted order: for a sorted pair (lower, higher), it's a legal trade exactly when the higher price's year comes *before* the lower price's year — then the candidate loss is higher − lower. The minimum such difference is the answer. O(n log n) from the sort; prices reach 10¹⁶ so use long.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realize that after sorting by price, the minimum loss must be between two consecutive prices — and that you still need the original years attached to enforce 'buy earlier, sell later'.

Where candidates slip

Comparing all O(n²) pairs, forgetting the temporal direction (buy must precede sell), or using a 32-bit int when prices reach 10¹⁶.

How to stand out

Argue why only adjacent sorted prices matter: any non-adjacent valid pair has a price between them that forms a smaller valid difference. Mention the TreeSet streaming variant and call out the overflow before coding.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — All Ordered Pairs	`O(n²)`	`O(1)`	State it first to fix the definition of a valid loss, then note the O(n²) blowup at n = 2×10⁵.	Read
2	Sort by Price + Adjacent Scan (Optimal)Optimal	`O(n log n)`	`O(n)`	The answer they want: sort prices, keep years, and only consecutive sorted prices can be the minimum loss.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewPair each price with its yearyear(higher) < year(lower)?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — All Ordered Pairs

TimeO(n²)SpaceO(1)

State it first to fix the definition of a valid loss, then note the O(n²) blowup at n = 2×10⁵.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What makes a pair (i, j) a valid losing trade? Spell out both the time order and the price order.

2Hint 2Explore hint

Try every pair with i < j; keep it only when price[i] > price[j].

3Hint 3Explore hint

Track the minimum of price[i] − price[j] over all valid pairs.

A · Core idea

The literal reading of the problem: a valid trade is a pair of years i < j where price[i] > price[j], and the loss is price[i] − price[j]. Enumerate every such pair and keep the smallest loss.

Why both conditions matter. i < j enforces buy-then-sell in time; price[i] > price[j] enforces that it's a loss, not a gain. Drop either and you count illegal trades.

Use long throughout. Prices reach 10¹⁶, so both the values and the differences must be 64-bit. A 32-bit int silently wraps.

Why we don't ship it. With n up to 2×10⁵, n²/2 ≈ 2×10¹⁰ comparisons — far too slow. Sorting reveals that only a handful of candidate pairs ever matter.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

price = [20, 7, 8, 2, 5]

Array state

buy i=1 (7)

sell j=4 (5) → loss 2

[0]

i ↓

[1]

[2]

[3]

j ↓

[4]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

Reference implementation previewpublic long minimumLossBrute(long[] price) { int n = price.length; long best = Long.MAX_VALUE; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) {Explore the full code

solution.javaJava

Brute Force — All Ordered Pairs — reference

3 teaching notes

1
public long minimumLossBrute(long[] price) {
2
    int n = price.length;
3
    // long because prices and differences reach 10¹⁶.
4
    long best = Long.MAX_VALUE;
5
    for (int i = 0; i < n; i++) {
6
        // j > i guarantees the sale happens in a later year than the purchase.
7
        for (int j = i + 1; j < n; j++) {
8
            // Only losing trades qualify — buy price strictly above sell price.
9
            if (price[i] > price[j]) {
10
                best = Math.min(best, price[i] - price[j]);
11
            }
12
        }
13
    }
14
    return best;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Most of the O(n²) pairs are wasteful: a buy price that's far above the sell price can never be the minimum loss. Only prices close in value can produce a small loss — which is precisely what sorting surfaces.

ComplexityO(n²) time, O(1) space — Two nested loops over all i < j → n(n−1)/2 ≈ n²/2 pairs, O(n²).

E · Edge cases and pitfalls3Allowing j ≤ i — sells before or at the buy year.Explore edge cases

Pitfalls

Allowing j ≤ i — sells before or at the buy year.
Using int for prices — overflow at 10¹⁶.
Running O(n²) on n = 2×10⁵ and timing out.

03.2

Approach 2 of 2 · Optimal

Sort by Price + Adjacent Scan (Optimal)

TimeO(n log n)SpaceO(n)

The answer they want: sort prices, keep years, and only consecutive sorted prices can be the minimum loss.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If two valid prices are far apart in value, can their gap be the minimum loss? What if some other price sits between them?

2Hint 2Explore hint

Sort the (price, year) pairs by price. For a consecutive pair, the smaller difference is between adjacent prices.

3Hint 3Explore hint

A consecutive pair (lower, higher) is a legal trade only when the higher price's year is earlier than the lower price's year. Take the min of those differences.

A · Core idea

Sort the prices ascending, carrying each price's original year. Now walk consecutive pairs. For a sorted pair (lower, higher), the only way it's a valid trade is to buy the higher price and sell the lower — and that requires the higher price's year to be earlier than the lower price's year. If so, the candidate loss is higher − lower.

Why only adjacent pairs matter. Suppose the optimal trade buys at price H and sells at price L with H > L. Take any other price X with L < X < H. If X's year is before L's year, then buying X and selling L is also valid and gives a smaller loss (X − L < H − L) — contradicting optimality. Otherwise X's year is after L's year; but X < H, and if X's year is after the buy year of H then selling X (instead of L) against H... the careful version of this argument shows the minimum loss is always realized by two prices with no other price strictly between them — i.e. consecutive in sorted order. So we never need non-adjacent pairs.

Why we keep the year. Sorting by price throws away the time order, but the trade legality depends entirely on it. Storing (price, year) lets us check year(higher) < year(lower) in O(1) per pair.

Why long. Prices reach 10¹⁶; the differences do too. Use 64-bit for the stored prices and the running best.

Streaming variant (TreeSet). Equivalently, process prices in year order while maintaining an ordered set of prices seen in earlier years. For each new (sell) price, query the smallest stored price strictly greater than it (a higher, earlier buy) and take that difference. Same O(n log n), handy when prices arrive one at a time.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

price = [20, 7, 8, 2, 5]

Array state

pair (5, 7)

year(7)=2 < year(5)=5 → loss 7−5 = 2

[0]

lo ↓

[1]

hi ↓

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Sort by Price + Adjacent Scan (Optimal) — optimal

3 teaching notes

1
public long minimumLoss(long[] price) {
2
    int n = price.length;
3
    long[][] pe = new long[n][2];   // [price, originalYearIndex]
4
    for (int i = 0; i < n; i++) {
5
        pe[i][0] = price[i];
6
        // Stash the original year alongside the price before sorting destroys
7
        // positional order.
8
        pe[i][1] = i;
9
    }
10
    java.util.Arrays.sort(pe, (x, y) -> Long.compare(x[0], y[0]));
11
    long best = Long.MAX_VALUE;
12
    for (int k = 1; k < n; k++) {
13
        long higher = pe[k][0],     hiYear = pe[k][1];
14
        long lower  = pe[k - 1][0], loYear = pe[k - 1][1];
15
        if (hiYear < loYear) {       // buy higher earlier, sell lower later
16
            // Adjacent sorted prices give the smallest possible positive gap.
17
            best = Math.min(best, higher - lower);
18
        }
19
    }
20
    return best;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

Sorting converts a global 'compare every pair' into a local 'compare neighbors' problem — the minimum gap between any two values is always between adjacent values once sorted. The only twist here is the temporal constraint, which we preserve by carrying the original index. This 'sort then look at neighbors' move is the backbone of closest-pair and minimum-difference problems.

ComplexityO(n log n) time, O(n) space — Sorting dominates at O(n log n). The adjacent scan is one O(n) pass. Storing (price, year) pairs is O(n) space.

E · Edge cases and pitfalls5price = [2, 3, 4, 1] — Sorted [1,2,3,4]; pair (1,2): year(2)=0 < year(1)=3 → loss 1. That beats all larger adjacent gaps.Explore edge cases

Edge cases handled

price = [2, 3, 4, 1]Sorted [1,2,3,4]; pair (1,2): year(2)=0 < year(1)=3 → loss 1. That beats all larger adjacent gaps.
price = [5, 10, 3]Sorted [3,5,10]; pair (3,5): year(5)=0 < year(3)=2 → loss 2. Pair (5,10) has year(10)=1 > year(5)=0, skipped.

Pitfalls

Sorting only the prices and losing the original years — you can't check buy-before-sell.
Checking the wrong direction: it must be year(higher) < year(lower), not the reverse.
Using int for prices/loss — 10¹⁶ overflows; use long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long minimumLoss(long[] price) { int n = price.length; long[][] pe = new long[n][2]; // [price, originalYearIndex] for (int i = 0; i < n; i++) { pe[i][0] = price[i];Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Losing the year when sorting

Sorting only the price values discards the time order, so you can no longer tell whether the higher price was bought earlier than the lower price was sold.

Explore the code comparison

Don't write this

prices = sorted(price)            # year information gone

Write this instead

order = sorted(range(len(price)), key=lambda i: price[i])  # keeps years

Wrong temporal direction

A valid loss buys the HIGHER price first and sells the LOWER price later. Checking year(lower) < year(higher) flips the trade and counts impossible transactions.

Explore the code comparison

Don't write this

if (loYear < hiYear) {            // sell-then-buy — illegal
    best = Math.min(best, higher - lower);
}

Write this instead

if (hiYear < loYear) {            // buy higher earlier, sell lower later
    best = Math.min(best, higher - lower);
}

32-bit overflow on prices

Prices go up to 10¹⁶, far beyond Integer.MAX_VALUE (~2.1×10⁹). Storing or subtracting them as int corrupts the result.

Explore the code comparison

Don't write this

int[] price = ...; int best = Integer.MAX_VALUE;

Write this instead

long[] price = ...; long best = Long.MAX_VALUE;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort by price; minimal loss lives between consecutive prices

Code pattern to memorize

pair (price, year); sort by price asc
best = +inf
for k in 1..n-1:
    hi = sorted[k], lo = sorted[k-1]
    if year(hi) < year(lo):   # bought higher earlier, sold lower later
        best = min(best, price(hi) - price(lo))
return best

Rules to remember

1You buy first, sell later — the higher (buy) price must have the earlier year; the lower (sell) price the later year.
2The minimum loss always occurs between two consecutive prices in sorted order — no need to check non-adjacent pairs.
3All prices are distinct, so 'consecutive in sorted order' is well-defined and the difference is strictly positive.
4Keep the original year/index alongside the price when you sort — that's how you check the buy-before-sell ordering.
5Prices reach 10¹⁶ — use long (64-bit) for prices and the loss, an int overflows.

Use this pattern when

Minimize a positive difference between two elements subject to an ordering (time) constraint
'Closest pair' style questions where adjacency in sorted order limits candidates
Buy-low/sell-high or buy-high/sell-low with a temporal direction

Choose another pattern when

No ordering constraint between the two elements → it's just min adjacent difference after sorting
Many queries / streaming inserts where you need the best so far each step → an ordered set (TreeSet) is cleaner than a one-shot sort
You may sell at a profit too → this is the classic max-profit stock problem, a different DP/greedy

Interview takeaway

Sort by value and only adjacent pairs can give the minimum difference. Carry the original index so you can enforce the time ordering, and the loss-minimization collapses from O(n²) pair-checking to a single O(n) scan after the sort.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternSort-then-neighbors for minimum difference, plus an index carried through the sort to honor an ordering constraint. The minimum positive gap between values is always between adjacent sorted values; a TreeSet gives the streaming version. Same backbone as Minimum Absolute Difference and closest-pair problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Minimum Loss with non-distinct prices
Coming soon
If duplicates are allowed, break ties by year and use an ordered multiset / TreeMap with counts.
Best Time to Buy and Sell Stock
Coming soon
The profit-maximizing mirror — track the running minimum buy price in one pass.
Minimum Absolute Difference in an Array
Coming soon
Same 'sort then compare neighbors' core, without the temporal constraint.

Same pattern

←

Maximum Subarray Sum

Continue · Next problem

Sherlock and Array

mediumArraysSometimes asked

Minimum Loss

Arrays & Hashing · 76 of 83 · 9 min

Given the prices indexed by year, find the minimum loss Lauren can incur. It is guaranteed that at least one losing transaction is possible, and all prices are distinct.

In plain English

Examples

Example 1

Input: price = [20, 7, 8, 2, 5]
Output: 2
Note: Buy at 7 (year 2), sell at 5 (year 5): loss 2. That's the smallest loss among all buy-earlier/sell-later pairs.

Example 2

Input: price = [2, 3, 4, 1]
Output: 1
Note: Buy at 2 (year 1), sell at 1 (year 4): loss 1. Smaller than buying at 3 or 4 and selling the final 1.

Example 3

Input: price = [5, 10, 3]
Output: 2
Note: Buy at 5 (year 1), sell at 3 (year 3): loss 2. Buying at 10 (year 2) and selling 3 gives a larger loss of 7.

Constraints

1 ≤ n ≤ 2×10⁵
1 ≤ price[i] ≤ 10¹⁶
All prices are distinct
At least one valid (buy earlier, sell later at a loss) transaction exists

Clarifying questions4First question: Must the sale happen in a later year than the purchase?Explore questions

Q1.Must the sale happen in a later year than the purchase?
Yes. Buy at an earlier index, sell at a later index. The higher (buy) price must therefore have the smaller original index.
Q2.Is selling at a profit allowed?
No — only losing transactions count. We minimize a strictly positive loss, never a gain.
Q3.Are prices guaranteed distinct?
Yes. That makes sorting unambiguous and every adjacent difference strictly positive.
Q4.How large can prices get?
Up to 10¹⁶, which exceeds the 32-bit range. Use 64-bit integers for prices and the computed loss.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realize that after sorting by price, the minimum loss must be between two consecutive prices — and that you still need the original years attached to enforce 'buy earlier, sell later'.

Where candidates slip

Comparing all O(n²) pairs, forgetting the temporal direction (buy must precede sell), or using a 32-bit int when prices reach 10¹⁶.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — All Ordered Pairs	`O(n²)`	`O(1)`	State it first to fix the definition of a valid loss, then note the O(n²) blowup at n = 2×10⁵.	Read
2	Sort by Price + Adjacent Scan (Optimal)Optimal	`O(n log n)`	`O(n)`	The answer they want: sort prices, keep years, and only consecutive sorted prices can be the minimum loss.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — All Ordered Pairs

TimeO(n²)SpaceO(1)

State it first to fix the definition of a valid loss, then note the O(n²) blowup at n = 2×10⁵.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What makes a pair (i, j) a valid losing trade? Spell out both the time order and the price order.

2Hint 2Explore hint

Try every pair with i < j; keep it only when price[i] > price[j].

3Hint 3Explore hint

Track the minimum of price[i] − price[j] over all valid pairs.

A · Core idea

The literal reading of the problem: a valid trade is a pair of years i < j where price[i] > price[j], and the loss is price[i] − price[j]. Enumerate every such pair and keep the smallest loss.

Why both conditions matter. i < j enforces buy-then-sell in time; price[i] > price[j] enforces that it's a loss, not a gain. Drop either and you count illegal trades.

Use long throughout. Prices reach 10¹⁶, so both the values and the differences must be 64-bit. A 32-bit int silently wraps.

Why we don't ship it. With n up to 2×10⁵, n²/2 ≈ 2×10¹⁰ comparisons — far too slow. Sorting reveals that only a handful of candidate pairs ever matter.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

price = [20, 7, 8, 2, 5]

Array state

buy i=1 (7)

sell j=4 (5) → loss 2

[0]

i ↓

[1]

[2]

[3]

j ↓

[4]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Brute Force — All Ordered Pairs — reference

3 teaching notes

1
public long minimumLossBrute(long[] price) {
2
    int n = price.length;
3
    // long because prices and differences reach 10¹⁶.
4
    long best = Long.MAX_VALUE;
5
    for (int i = 0; i < n; i++) {
6
        // j > i guarantees the sale happens in a later year than the purchase.
7
        for (int j = i + 1; j < n; j++) {
8
            // Only losing trades qualify — buy price strictly above sell price.
9
            if (price[i] > price[j]) {
10
                best = Math.min(best, price[i] - price[j]);
11
            }
12
        }
13
    }
14
    return best;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — Two nested loops over all i < j → n(n−1)/2 ≈ n²/2 pairs, O(n²).

E · Edge cases and pitfalls3Allowing j ≤ i — sells before or at the buy year.Explore edge cases

Pitfalls

Allowing j ≤ i — sells before or at the buy year.
Using int for prices — overflow at 10¹⁶.
Running O(n²) on n = 2×10⁵ and timing out.

03.2

Approach 2 of 2 · Optimal

Sort by Price + Adjacent Scan (Optimal)

TimeO(n log n)SpaceO(n)

The answer they want: sort prices, keep years, and only consecutive sorted prices can be the minimum loss.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If two valid prices are far apart in value, can their gap be the minimum loss? What if some other price sits between them?

2Hint 2Explore hint

Sort the (price, year) pairs by price. For a consecutive pair, the smaller difference is between adjacent prices.

3Hint 3Explore hint

A consecutive pair (lower, higher) is a legal trade only when the higher price's year is earlier than the lower price's year. Take the min of those differences.

A · Core idea

Why long. Prices reach 10¹⁶; the differences do too. Use 64-bit for the stored prices and the running best.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

price = [20, 7, 8, 2, 5]

Array state

pair (5, 7)

year(7)=2 < year(5)=5 → loss 7−5 = 2

[0]

lo ↓

[1]

hi ↓

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Sort by Price + Adjacent Scan (Optimal) — optimal

3 teaching notes

1
public long minimumLoss(long[] price) {
2
    int n = price.length;
3
    long[][] pe = new long[n][2];   // [price, originalYearIndex]
4
    for (int i = 0; i < n; i++) {
5
        pe[i][0] = price[i];
6
        // Stash the original year alongside the price before sorting destroys
7
        // positional order.
8
        pe[i][1] = i;
9
    }
10
    java.util.Arrays.sort(pe, (x, y) -> Long.compare(x[0], y[0]));
11
    long best = Long.MAX_VALUE;
12
    for (int k = 1; k < n; k++) {
13
        long higher = pe[k][0],     hiYear = pe[k][1];
14
        long lower  = pe[k - 1][0], loYear = pe[k - 1][1];
15
        if (hiYear < loYear) {       // buy higher earlier, sell lower later
16
            // Adjacent sorted prices give the smallest possible positive gap.
17
            best = Math.min(best, higher - lower);
18
        }
19
    }
20
    return best;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n log n) time, O(n) space — Sorting dominates at O(n log n). The adjacent scan is one O(n) pass. Storing (price, year) pairs is O(n) space.

E · Edge cases and pitfalls5price = [2, 3, 4, 1] — Sorted [1,2,3,4]; pair (1,2): year(2)=0 < year(1)=3 → loss 1. That beats all larger adjacent gaps.Explore edge cases

Edge cases handled

price = [2, 3, 4, 1]Sorted [1,2,3,4]; pair (1,2): year(2)=0 < year(1)=3 → loss 1. That beats all larger adjacent gaps.
price = [5, 10, 3]Sorted [3,5,10]; pair (3,5): year(5)=0 < year(3)=2 → loss 2. Pair (5,10) has year(10)=1 > year(5)=0, skipped.

Pitfalls

Sorting only the prices and losing the original years — you can't check buy-before-sell.
Checking the wrong direction: it must be year(higher) < year(lower), not the reverse.
Using int for prices/loss — 10¹⁶ overflows; use long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Losing the year when sorting

Sorting only the price values discards the time order, so you can no longer tell whether the higher price was bought earlier than the lower price was sold.

Explore the code comparison

Don't write this

prices = sorted(price)            # year information gone

Write this instead

order = sorted(range(len(price)), key=lambda i: price[i])  # keeps years

Wrong temporal direction

A valid loss buys the HIGHER price first and sells the LOWER price later. Checking year(lower) < year(higher) flips the trade and counts impossible transactions.

Explore the code comparison

Don't write this

if (loYear < hiYear) {            // sell-then-buy — illegal
    best = Math.min(best, higher - lower);
}

Write this instead

if (hiYear < loYear) {            // buy higher earlier, sell lower later
    best = Math.min(best, higher - lower);
}

32-bit overflow on prices

Prices go up to 10¹⁶, far beyond Integer.MAX_VALUE (~2.1×10⁹). Storing or subtracting them as int corrupts the result.

Explore the code comparison

Don't write this

int[] price = ...; int best = Integer.MAX_VALUE;

Write this instead

long[] price = ...; long best = Long.MAX_VALUE;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort by price; minimal loss lives between consecutive prices

Code pattern to memorize

pair (price, year); sort by price asc
best = +inf
for k in 1..n-1:
    hi = sorted[k], lo = sorted[k-1]
    if year(hi) < year(lo):   # bought higher earlier, sold lower later
        best = min(best, price(hi) - price(lo))
return best

Rules to remember

1You buy first, sell later — the higher (buy) price must have the earlier year; the lower (sell) price the later year.
2The minimum loss always occurs between two consecutive prices in sorted order — no need to check non-adjacent pairs.
3All prices are distinct, so 'consecutive in sorted order' is well-defined and the difference is strictly positive.
4Keep the original year/index alongside the price when you sort — that's how you check the buy-before-sell ordering.
5Prices reach 10¹⁶ — use long (64-bit) for prices and the loss, an int overflows.

Use this pattern when

Minimize a positive difference between two elements subject to an ordering (time) constraint
'Closest pair' style questions where adjacency in sorted order limits candidates
Buy-low/sell-high or buy-high/sell-low with a temporal direction

Choose another pattern when

No ordering constraint between the two elements → it's just min adjacent difference after sorting
Many queries / streaming inserts where you need the best so far each step → an ordered set (TreeSet) is cleaner than a one-shot sort
You may sell at a profit too → this is the classic max-profit stock problem, a different DP/greedy

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Minimum Loss with non-distinct prices
Coming soon
If duplicates are allowed, break ties by year and use an ordered multiset / TreeMap with counts.
Best Time to Buy and Sell Stock
Coming soon
The profit-maximizing mirror — track the running minimum buy price in one pass.
Minimum Absolute Difference in an Array
Coming soon
Same 'sort then compare neighbors' core, without the temporal constraint.

Same pattern

←

Maximum Subarray Sum

Continue · Next problem

Sherlock and Array