Python O(N) complexity with simple explanation‼️
Intuition\nThe transactions can be divided into two kinds:\n1. transaction with positive profit.\n2. transaction with non-positive profit.\n\nTo find the minimu
# Intuition\nThe transactions can be divided into two kinds:\n1. transaction with positive profit.\n2. transaction with non-positive profit.\n\nTo find the minimum money required before transactions, we only need to know how much money we can lose in the worst case. The worst case is just **first completing all transactions with non-positive profit and then completing the rest**. \n\nWe use `lost` to store the money we lose by completing all transactions with non-positive profit.\n\nBesides, among all those transactions with non-negative profit, we need to find the largest cashback, i.e., `large_gain`. A possible maximum of money lost is `lost` + `large_gain`.\n\nAmong all those transactions with positive profit, we need to find the largest cost, i.e., `large_cost`. The other possible maximum of money lost is `lost` + `large_cost`.\n\nHence, the money required is min(`lost` + `large_gain`, `lost` + `large_cost`).\n\n\n# Code\n```\nclass Solution(object):\n    def minimumMoney(self, transactions):\n        """\n        :type transactions: List[List[int]]\n        :rtype: int\n        """\n        large_gain = -1\n        large_cost = -1\n        lost = 0\n\n        for x in transactions:\n            if x[0]>=x[1]: # non-postive profit\n                lost += x[0] - x[1]\n                large_gain = max(large_gain, x[1])\n            else: # positive profit\n                large_cost = max(large_cost, x[0])\n        return max(lost + large_gain, lost + large_cost)\n\n\n\n            \n        \n\n```
['Python']