Greedy, Java, Explained in details
Intuition\nAll the transactions where cashback is bigger than cost can be ignored for starters, because once we start doing them our money deposit will increase
# Intuition\nAll the transactions where cashback is bigger than cost can be ignored for starters, because once we start doing them our money deposit will increase, so until that point money will only decrease when we process transactions where cost > cashback. However, we only care about one transaction with cost < cashback, because before we received any cashback we need to have enough money to get around the cost of this transaction, that\'s why we need to find maximum such cost to finally add it.\n\n# Approach\nFinally there are 2 cases:\nCase 1: All transactions with cost >= cashback, in this case we finally need to add up cashback before we made the final transaction and the cashback should as big as possible.\nCase 2: There exists transaction where cost < cashback, in this case we actually only add the biggest cost from transactions array where cost < cashback to maximize result.\nFinally it turns out that we end up to choosing the maximum of cashback from case 1 and cost from case 2. If you look at it closely you can either choose not getting a cashback and leave yourself with paid cost, or get a cashback and pay a cost from the other transaction from case 2.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\n```\nclass Solution {\n    public static long minimumMoney(int[][] transactions) {\n        long sum = 0;\n        int maxCashback = -1;\n        int maxCost = -1;\n        for (int[] transaction : transactions) {\n            sum += Math.max(0, transaction[0] - transaction[1]);\n            if (transaction[0] - transaction[1] >= 0) {\n                maxCashback = Math.max(maxCashback, transaction[1]);\n            }\n            if (transaction[0] - transaction[1] < 0) {\n                maxCost = Math.max(maxCost, transaction[0]);\n            }\n        }\n        return sum + Math.max(maxCashback, maxCost);\n    }\n}\n```
['Greedy', 'Java']