860. Lemonade Change

Time: O(n)

Space: O(1)

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

1Count five and ten dollar bills.
2$5 → five++.
3$10 → if five==0 return false; five--, ten++.
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

// 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?