Python:  Follow the Hints
Intuition\n Describe your first thoughts on how to solve this problem. \nOverall, we want to figure out how much money we need up front to ensure that we have e
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nOverall, we want to figure out how much money we need up front to ensure that we have enough money before we try processing any transaction to pay for its cost, regardless of whether we get a big "cashback" or not.  And, we want to do this for *any* order of transaction.  Does that mean we have to try all orders?  No, but we need to figure out what the worst order would be.\n\nThe hints describe how to split the transactions into two classes which I called ```incomers``` (cost <= cashback) and ```outgoers``` (cost > cashback).  It *appears* that the worst order is sorting the two classes as suggested and then doing all the ```outgoers``` and then all the ```incomers```; I actually tried the opposite way at first and found that it passed some but not most of the test cases.\n\nSo, first the ```outgoers```:  Since every transaction has a cost greater than the cashback, as we do more and more of them, our cash on hand gets less and less.  In fact, it hits a low point just after we pay the cost for the last outgoer but before we get its cashback.\nThat gives us a first estimate about how much we need up front, which is called ```min_ante``` in the code.  If we have ```min_ante``` to start with, we can process all the ```outgoers``` and end up with the cashback from the last outgoer in our pocket.\n\nNext, we have to process the ```incomers```.  Because these transactions all have cost no more than cashback, as we process more and more of the ```incomers``` we never fall behind and may even make up some cash in the process.  The only provision is that we have to have up front the cost of the most expensive incomer, called ```min_incomer_available``` in the code  If the money we had after processing the ```outgoers``` doesn\'t cover that amount, then we have to increase the up front investment ```min_ante``` by the shortfall.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe code is a pretty straightforward implementation of the Hints and Intuition.  One thing I learned during the implementation was that it was possible that the ```incomers``` or the ```outgoers``` might be empty.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nWe have to process all the ```outgoers``` to compute ```min_ante``` and ```after_outgoers```.  However, we only need to look at the first of the ```incomers```.  The overall time complexity is $$O(n)$$ where $$n$$ is the number of transactions.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe non-scalar storage used includes space for ```incomers``` and ```outgoers```, which gives a space complexity of $$O(n)$$.\n# Code\n```\nclass Solution:\n    def minimumMoney(self, transactions: list[list[int]]) -> int:\n        # First, split and sort the input "transactions" per the hint\n        incomers = [transaction for transaction in transactions if transaction[0] <= transaction[1]]\n        outgoers = [transaction for transaction in transactions if transaction[0] > transaction[1]]\n        incomers.sort(key=lambda transaction: transaction[0], reverse=True)\n        outgoers.sort(key=lambda transaction: transaction[1])\n\n        # Second, process "outgoers", transactions where cost > cashback:  The question is:  how\n        # much money do we need up front in order to complete processing of\n        # the outgoers.   The latter amount is the sum of the net cost of all but the last\n        # transaction plus the cost of the last transaction.\n        if outgoers:\n            outgoer_cost = sum(map(lambda transaction: transaction[0] - transaction[1], outgoers) )\n            assert outgoer_cost > 0\n            min_ante = outgoer_cost + outgoers[-1][1]\n            after_outgoers = min_ante - outgoer_cost\n        # What this means:  If we start with "min_ante", we can process all the "outgoers" and\n        # end up with "after_outgoers".\n        else:\n            min_ante = 0\n            after_outgoers = 0\n\n        # Third, process the "incomers", transactions where cashback is >= cost.  I *think* it\'s enough\n        # to have enough cash on hand to satisfy the first "cost" since then, by construction, we\'ll\n        # have enough for all subsequent "incomers".\n        if incomers:\n            min_incomer_available = incomers[0][0]\n        else:\n            min_incomer_available = 0\n\n        # Fourth, put together the two components:\n        if min_incomer_available > after_outgoers:\n            min_ante += min_incomer_available - after_outgoers\n        return min_ante\n```
['Python3']