The easiest possible explanation you are looking for
It took me a while to get this through my head. So take your time but make sure you understand this.\n\nAlse note that this is not the perfect O(N) solution. Yo
It took me a while to get this through my head. So take your time but make sure you understand this.\n\n**Alse note that this is not the perfect O(N) solution. You can see Lee215 soln for that. This is O(NlogN) solution but this is what was easier for me to understand**\n\n**Now lets start**\n\n1. First, know that there are 2 kinds of transaction, one where you earn more than you spend (good transactions), and one where you earn less than you spend (bad transactions).\n2.  In the worst case, you will need to perform all the bad transactions at first. What would be even worse? You will have to perform the worst bad transaction first. What does that mean? It means, the transaction, that gives you the least cashback among all bad transactions.\n3.  Now that the bad transactions are over, now we will perform the good transactions. Now what can be the worst case here? It can be that you need to perform the costliest transaction among the good transactions first. But once you have done the costliest transaction, you no longer need to check the further transactions. Why so? Because this is a good transaction. If you  spend say 10$, you are guaranteed to receive a cashback of 10$ or more. And since this was the costliest transaction among the good transaction, you will now have money for the rest of them anyway, so no need to consider them.\n\n**Lets take an example to understand even better**\n\nwe are given this transaction array :`[[7,2],[0,10],[5,0],[4,1],[5,8],[5,9]]`\nLets separate the good and bad transactions.\n\n**good transactions** :`[[0,10],[5,8],[5,9]]`\n**bad transactions** :`[[7,2],[5,0],[4,1]]`\n\nNow cosider the **bad transactions**:\n\tWhich one among `[[7,2],[5,0],[4,1]]` is the worst transaction you might have to make? The answer to that is `[5,0]`. **Why?** because you are spending 5$ and getting nothing in return. What will be the next worst transaction? It will be `[4,1]` for the same reason. Do you see the **pattern**?\n\t\nWe do the transaction with the least amount of cashback first. Because there we need to have our own money and can\'t rely on cashback. So if we follow this,\n**First transaction:** `cur += 5` = 5; `need = max(need,cur)` = 5; `cur -= 0` = 5\n**Second transaction:** `cur += 4` = 9; `need = max(need,cur)` = 9; `cur -= 1` = 8  ( **NOTE** the need will first become 9, because we get a cashback only after paying the cost first. So in order to make the first and the second transaction, you need minimum of 9$)\n**Third transaction:** `cur += 7` = 15;  `need = max(need,cur)` = 15; `cur -= 2` = 13\n\n**Okay so at this point all the bad transactions are over and everything bad that could have happened has happened... Except one\uD83D\uDE05**\nEven though we only have good transactions now, we need to pay the cost for them to recieve the cashback. This is simpler though. We only need to figure out which is the costliest good transaction. **Why?** because once we pay that amount, we know since its a good transaction, we will get atleast the same amount back if not more.\n\nSo the ***worst*** **good transaction** is `[5,8] or [5,9]`. `cur += 5` = 18; `need = max(need,cur)` = 18\n\nAnd we got our answer. We need a minimum of 18$ in order to complete all transaction in any order!\n\n**Let\'s finally have a look at the code to solidify what I just explained**\n\n```\ndef minimumMoney(self, transactions: List[List[int]]) -> int:\n        \n\tgoodTransactions = [txn for txn in transactions if txn[0] <= txn[1]]\n\tbadTransactions = [txn for txn in transactions if txn[0] > txn[1]]\n\n\tbadTransactions.sort(key=lambda x: x[1])\n\n\tneed = 0\n\tcur_amount = 0\n\n\tfor cost,cashback in badTransactions:\n\t\tcur_amount += cost\n\t\tneed = max(need,cur_amount)\n\t\tcur_amount -= cashback\n\n\tif goodTransactions:\n\t\tcostliest_good_transaction = max(goodTransactions, key=lambda x: x[0])\n\t\tcur_amount += costliest_good_transaction[0]  \n\t\tneed = max(need, cur_amount)\n\n\treturn need\n```\t\t\n\n***If this post was helpful at all, pls do upvote : )***
['Greedy', 'Python3']