💬 Discord
Sign In
NeetCode #763LC-860EasyGreedyNC 250
← Back to All Problems

#763 · #860 · Lemonade Change(柠檬水找零)

📌 Problem Statement & Constraints

Each customer in a queue pays with a 5, 10 or 20 dollar bill for a 5 dollar lemonade. You start with no change. Return true if you can give every customer correct change, processing them in order. Constraints: 1 <= bills.length <= 10^4, bills[i] is 5, 10 or 20.

💡 Core Algorithmic Approaches

  1. Only the counts of 5 and 10 bills matter; 20 bills are never useful as change.
  2. A 5 needs no change; a 10 needs one 5; a 20 needs either a 10 plus a 5 or three 5 bills.
  3. For a 20, prefer the 10 + 5 combination because it preserves scarce 5 bills.
  4. If any payment cannot be made, return false immediately.

💻 Benchmark Python3 Implementation

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = ten = 0
        for b in bills:
            if b == 5:
                five += 1
            elif b == 10:
                if five == 0:
                    return False
                five -= 1
                ten += 1
            else:                          # 20
                if ten > 0 and five > 0:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): two counters.

⚠️ Interview Pitfalls & Follow-ups

  • Giving three 5 bills for a 20 when a 10 + 5 is available: this wastes 5 bills that later customers may need.
  • Tracking 20 bills: they can never be handed back as change, so counting them is pointless.
  • Processing customers out of order: the queue order is fixed and matters.
  • Forgetting that a 10 also requires a 5 in change: a 10 payment must be settled with exactly one 5.