- we need a way or recording what types of bills are collected as we sell
- a fixed size vector to record the frequency of bill types (5,10,20)
🤔What Did I Struggle With?
~
💡 Explanation of Solution
for each bill / sales:
- if the bill is a 5, increment the first element in the array and continue as no change is required
- if the bill is a 10, check if there are any 5s available, if not return false
- if the bill is a 20, check if there is a 10 and 5, then check if there are 3 5s, if neither return false
⌛ Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1) since our frequency vector is fixed in size (3)
💻 Implementation of Solution
class Solution {public: bool lemonadeChange(vector<int>& bills) { vector<int> change(3, 0); // change[0] = count of 5s, change[1] = count of 10s, change[2] = count of 20s for (int bill : bills) { if (bill == 5) { change[0]++; // Increment count of 5s } else if (bill == 10) { if (change[0] > 0) { change[0]--; // Use one 5 to give change change[1]++; // Increment count of 10s } else { return false; // Not enough change } } else if (bill == 20) { // First try to give change using one 10 and one 5 if (change[1] > 0 && change[0] > 0) { change[1]--; change[0]--; } // Otherwise, try to give change using three 5s else if (change[0] >= 3) { change[0] -= 3; } else { return false; // Not enough change } } } return true; // Successfully gave change for all customers }};