← DSA Atlas
Dedicated problem page · #860

Lemonade Change

MediumGreedy AlgorithmsGreedy Algorithms
Solve on LeetCode ↗
860
MediumGreedy AlgorithmsGreedy AlgorithmsPattern-guided

Lemonade Change

Solve LeetCode #860, “Lemonade Change.” Read the official prompt once, then return here to turn its requirements into the greedy algorithms pattern.

Open official problem prompt ↗
In plain English

Learn how to translate “Lemonade Change” into a precise state, transition, and stopping condition before committing to code.

Picture it like this

Treat the prompt like a route on a map: Greedy Algorithms is the map legend, the invariant is your current location marker, and each code step must move you closer to the destination without losing what is already known.

Example
Input
Use the first example in the official prompt
Output
Predict the result before reading the explanation
Why
Trace how the greedy algorithms invariant transforms the input into the required answer.
Constraints
Identify the input shape and required return valueMark the largest constraint before choosing an approachConfirm that O(n log n) is appropriate for that constraint
Pattern lesson

See the pattern, then code

Greedy Algorithms
Recognition clue

A locally best action can be justified by an exchange argument or invariant.

↗
Greedy Algorithms

A locally best action can be justified by an exchange argument or invariant.. The chosen prefix is at least as extendable as any alternative prefix.

New words, made simpleKnow these before the algorithm
Signal
A phrase or constraint in the prompt that points toward Greedy Algorithms.
State
The smallest set of facts the algorithm must remember while it processes the input.
Invariant
The chosen prefix is at least as extendable as any alternative prefix.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Direct simulation or enumeration

Useful for a tiny example, but compare it with the largest constraint before coding.

Follow the wording literally and try every candidate, using it as a correctness baseline.

Time Usually quadratic or exponentialSpace Problem dependent
Best choiceGreedy Algorithms pattern

This is the recommended starting structure; adapt its state and return value to the official prompt.

Maintain this invariant: The chosen prefix is at least as extendable as any alternative prefix.

Time O(n log n)Space O(1) extra
The rule we keep true

Invariant

The chosen prefix is at least as extendable as any alternative prefix.

Why this is correct

Reasoning

The Greedy Algorithms template avoids repeating work by preserving exactly the information needed for the next decision. For “Lemonade Change,” prove that every update keeps the invariant true and that the final state matches the requested output.

The algorithm in three movesSay these aloud before coding
1Restate the prompt with a tiny hand-made example

Goal: Lemonade Change

2Name the state maintained by the greedy algorithms pattern

Pattern: Greedy Algorithms

3Trace one complete iteration before writing code

Invariant: The chosen prefix is at least as extendable as any alternative prefix.

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
Prompt0
State1
Choice2
Invariant3
Answer4
1 · ReadLeetCode #860: Lemonade Change
2 · AskWhat are the input, output, and largest constraint?
3 · Update stateTopic = Greedy Algorithms; tier = Core
4 · ResultWrite a one-sentence contract and reject approaches that exceed the constraint.
Key takeaway

Move from the raw prompt to a maintained invariant, then to the final answer.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 1Name the pattern operation

    Start from the reusable template, but rename the function and parameters to match the official prompt.

  2. 2
    Lines 1–3Define the state

    Locate the variables or data structure that remember everything needed for the next decision.

  3. 3
    Lines 5Find the transition

    This is where the current input changes the maintained state. Say the update aloud before editing it.

  4. 4
    Lines 7–9Connect state to the answer

    Adapt the template’s generic result to the exact return type and success condition in this problem.

  5. 5
    Lines 1–9Verify the contract

    Trace the official example and confirm the promised O(n log n) time and O(1) extra space bounds.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Use the smallest input allowed by the prompt.
  • Try an input where no candidate or transition succeeds, if the contract permits it.
  • Try duplicate, equal, empty, boundary, or maximum values relevant to the input type.
!

Common beginner mistakes

  • Copying the pattern template without adapting its state to this problem’s return value.
  • Choosing the pattern from the title alone instead of checking constraints and monotonicity.
  • Stating a complexity without counting every nested loop, data-structure operation, and recursion level.
Check your understanding

Before coding “Lemonade Change,” what invariant will you maintain, and which line of the prompt makes that invariant useful?

More in Greedy Algorithms

#45Jump Game IIGreedy BFS by reachable layers#53Maximum SubarrayRunning best-ending-here (Kadane)#55Jump GameGreedy farthest-reach#134Gas StationGreedy single pass with tank reset#135CandyTwo-pass greedy (left-to-right then right-to-left)#406Queue Reconstruction by HeightGreedy sort then insert by position