Java two approaches with Sorting | Greedy | Binary Searching
Approach - \n1. We must find the minimum money so that we can pass all the transactions performed in any order. So, with minimum money, we should be able to pas
**Approach** - \n1. We must find the minimum money so that we can pass all the transactions performed in any order. So, with minimum money, we should be able to pass the worst case possible after rearranging the given array.\n2. There can be two types of transactions possible.\n    2.1. First type are when cashback is less than cost. So, there will be loss of money after this transaction. We can call them loss ones.\n    2.2 Second type are when cashback is greater than or equal to cost, we will gain some money after this transaction. We can call them neutral ones.\n3. To create the worst we can think of executing the loss transactions before the neutral ones.\n4. Now, the question is what should be the order of loss and neutral ones.\n    4.1. If we arrange loss transactions in increasing order of their cashbacks. Then, we can think of one answer as the cost required to be able to pass the last of loss transaction arranged in inceasing order of their cashback. Because at this point, we will be most negative before accepting its cashback.\n    4.3. What if we arrange neutral ones in decreasing order of their cost. Then at the beginning of these type of transactions after completing all the loss transactions. We may need the most amount of starting money. Because after completing each of the neutral transaction, we will gain some money and the required starting money will decrease.\n5. So, now we have two possible answers. Compare and return the maximum value.\n6. We don\'t need to separate and create different list of for both types of transactions. If we observe carefully, we can think of the solution in linear with 1 traversal only.\n\nT.C is O(N) and S.C is O(1)\n```\nclass Solution {\n    public long minimumMoney(int[][] transactions) {\n        int maxCashBackForLoss = 0, maxCostForProfit = 0;\n        long total = 0l;\n        for(int i = 0; i<transactions.length; ++i){\n            if(transactions[i][0] > transactions[i][1]){\n                // Loss transaction\n                total += (transactions[i][0] - transactions[i][1]);\n                maxCashBackForLoss = (int)Math.max(maxCashBackForLoss, transactions[i][1]);\n            }\n            else{\n                maxCostForProfit = Math.max(maxCostForProfit, transactions[i][0]);\n            }\n        }\n        \n        long maxValue = 0l;\n        // maxValue = (long)Math.max(maxValue, total + maxCashBackForLoss);\n        // maxValue = (long)Math.max(maxValue, total + maxCostForProfit);\n        // return maxValue;\n        // Above code can be simplied to below single statement\n        return total + (long)Math.max(maxCashBackForLoss, maxCostForProfit);\n    }\n}\n\n```\n\n\nBelow approach is based as above one but uses binary search. It is slow as compared to above one but more intutive.\n\n**Approach** - \n1. Divide transactions into losses and gains with losses in increasing order of their cashback and gains in decreasing order of their cost. As discussed above.\n2. Then do binarySearch from 0l to Long.MAX_VALUE and try to pass both losses and gains for each mid value and shift end and start points of binary search accordingly.\n\nT.C is O(N*logN) and S.C is O(N)\n\n```\nclass Solution {\n    public long minimumMoney(int[][] transactions) {\n        List<Integer> losses = new ArrayList<>(), gains = new ArrayList<>();\n        for(int i = 0; i<transactions.length; ++i){\n            if(transactions[i][0] > transactions[i][1]){\n                losses.add(i);\n            }\n            else gains.add(i);\n        }\n        \n        Collections.sort(losses, (i1,i2)->transactions[i1][1] - transactions[i2][1]);\n        Collections.sort(gains, (i1,i2)->transactions[i2][0] - transactions[i1][0]);\n        \n        long start = 0l, end = Long.MAX_VALUE, mid, minValue = Long.MAX_VALUE;\n        while(start <= end){\n            mid = start + (end - start)/2;\n            if(check(losses, gains, mid, transactions)){\n                minValue = mid;\n                end = mid - 1;\n            }\n            else start = mid + 1;\n        }\n        \n        return minValue;\n    }\n    \n    private boolean check(List<Integer> losses, List<Integer> gains, long money, int[][] transactions){\n        for(int i : losses){\n            if(money < transactions[i][0]){\n                return false;\n            }\n            money = money - transactions[i][0] + transactions[i][1];\n        }\n        \n        for(int i : gains){\n            if(money < transactions[i][0]){\n                return false;\n            }\n            money = money - transactions[i][0] + transactions[i][1];\n        }\n        return true;\n    }\n}\n```
['Array', 'Greedy']