Beginner Friendly || Greedy Approach || Explanation ||
Intuition\nThe goal is to determine if we can provide correct change to every customer. We start with no money and can only make change with the bills we receiv
# Intuition\nThe goal is to determine if we can provide correct change to every customer. We start with no money and can only make change with the bills we receive. If a customer pays with a $5$ bill, no change is needed. If a customer pays with a $10$ bill, we need to give back $5$ as change. If a customer pays with a $20$ bill, we need to give $15$ back, preferably using one $10$ and one $5$ bill or three $5$ bills.\n\nThe key intuition is that when giving change, we should prioritize using the larger bills first. This is because larger bills will be more useful in future transactions that may require smaller bills as change.\n\n# Approach\n1. Initialize two variables `five` and `ten` to track the number of $5$ and $10$ bills we have.\n2. Iterate over the `bills` array:\n   - If the bill is $5$, increment the `five` counter since no change is required.\n   - If the bill is $10$, decrement the `five` counter by 1 to give $5$ as change and increment the `ten` counter.\n   - If the bill is $20$, check if we can give one $10$ and one $5$ as change (preferred). If not, check if we can give three $5$ bills. If neither is possible, return `false`.\n3. If we successfully process all customers, return `true`.\n\n# Complexity\n- **Time complexity**: \n  The time complexity is $$O(n)$$ where `n` is the number of bills in the input list. We process each bill exactly once in a single loop.\n\n- **Space complexity**: \n  The space complexity is $$O(1)$$ since we are using only a fixed amount of extra space for the `five` and `ten` variables, regardless of the size of the input.\n  \n\n# Code\n``` cpp []\nclass Solution {\npublic:\n    bool lemonadeChange(vector<int>& bills) {\n        unordered_map<int, int> track;\n        \n        for(int i = 0; i < bills.size(); i++){\n            if(bills[i] == 5) track[5]++;\n            else if(bills[i] == 10){\n                track[10]++;\n                if(track[5]) track[5]--;\n                else return false;\n            }\n            else{\n                if(track[10] && track[5]){\n                    track[10]--;\n                    track[5]--;\n                }\n                else if(track[5] >= 3){\n                    track[5] -= 3;\n                }\n                else return false;\n            }\n        }\n        return true;\n    }\n};\n```\n``` java []\nclass Solution {\n    public boolean lemonadeChange(int[] bills) {\n        int five = 0, ten = 0;\n\n        for (int bill : bills) {\n            if (bill == 5) {\n                five++;\n            } \n            else if (bill == 10) {\n                if (five == 0) return false;\n                five--;\n                ten++;\n            } \n            else {\n                if (ten > 0 && five > 0) {\n                    ten--;\n                    five--;\n                } \n                else if (five >= 3) {\n                    five -= 3;\n                } \n                else {\n                    return false;\n                }\n            }\n        }\n        return true;\n    }\n}\n```\n```python3 []\nclass Solution:\n    def lemonadeChange(self, bills: List[int]) -> bool:\n        five, ten = 0, 0\n        \n        for bill in bills:\n            if bill == 5:\n                five += 1\n            elif bill == 10:\n                if five == 0:\n                    return False\n                five -= 1\n                ten += 1\n            else:\n                if ten > 0 and five > 0:\n                    ten -= 1\n                    five -= 1\n                elif five >= 3:\n                    five -= 3\n                else:\n                    return False\n        \n        return True\n\n```
['Array', 'Greedy', 'C++', 'Java', 'Python3']