DDSA Solutions

860. Lemonade Change

EasyView on LeetCode
ArrayGreedy
Time: O(n)
Space: O(1)

Problem Overview

Greedy: maintain counts of $5 and $10 bills.

Intuition

Greedy: maintain counts of $5 and $10 bills. When customer pays $10, give $5 change. When customer pays $20, prefer $10+$5 over three $5s.

Algorithm

  1. 1Count five and ten dollar bills.
  2. 2$5 ? five++.
  3. 3$10 ? if five==0 return false; five--, ten++.
  4. 4$20 ? if ten>0 and five>0: ten--, five--; else if five>=3: five-=3; else return false.

Common Pitfalls

  • •For $20, prefer using $10+$5 change over three $5 bills to preserve $5 for future $10 customers.
860.cs
C#
// Approach: Greedily track $5 and $10 bill counts; for $20 change prefer using $10+$5 before falling back to three $5s.
// Time: O(n) Space: O(1)

public class Solution
{
    public bool LemonadeChange(int[] bills)
    {
        int cnt5 = 0, cnt10 = 0;

        foreach (int bill in bills)
        {
            if (bill == 5)
                cnt5++;
            else if (bill == 10)
            {
                cnt10++;
                cnt5--;
            }
            else
            {
                if (cnt10 > 0)
                {
                    cnt10--;
                    cnt5--;
                }
                else
                    cnt5 -= 3;
            }

            if (cnt5 < 0)
                return false;
        }

        return true;
    }
}
Was this solution helpful?

Related Problems