Easiest Hard Tag Question | Brute Force to Optimal
\nApproach 1\n\nExplanation \n\nwe have to sort the transactions array based on the increasing value of the cashback, of transactions\n\nnow you should notice o
\n**Approach 1**\n\n**Explanation** \n\nwe have to sort the transactions array based on the increasing value of the cashback, of transactions\n\nnow you should notice one thing we have to take all the transactions whose cost>cashback\nsee this test case, \n[[7,2],[0,10],[5,0],[4,1],[5,8],[5,9]]\n\nat the end , when we completely iterate our transactions array and our \nmax store value13 and ans store 15\n\nbut still there is one way by which we can increase our ans, \nif we add the maximum cost of transaction which we have not included yet\n\nmeans we can add maximum cost from [[0,10],[5,8],[5,9]],  \nthat is we can still add, 5 to our max and this may be the maximum ans\nand then update our ans as ans=Math.max(ans,max+ab);\n\n**TIME COMPLEXITY - Nlog(N)\nSPACE COMPLEXITY - O(1)**\n```\npublic long minimumMoney(int[][] transactions) {\n        Arrays.sort(transactions,(int a[],int b[])->(a[1]-b[1]));\n\n        long max=0,ans=0,ab=0;\n        for(int a[]:transactions){\n            if(a[0]>a[1]){\n                max+=a[0];\n                ans=Math.max(ans,max);\n                max-=a[1];\n            }\n            else ab=Math.max(ab,a[0]);\n        }\n        ans=Math.max(ans,max+ab);\n        return ans;\n    }\n```\n\t\n**Approach 2**\n\nExplanation\n\nIdea behind this approach is also the same,\n\nFor 2nd iteration i am just finding the sum of the differnce between the transactions where\ncost > cashback, because we have to consider that transactions.\n\nFor the first iteration our transaction array,  i am finding the last transaction that i should consider\nto create maximum ans possible,\n\nNow here we have a case \nThere is no transaction in which cost < cashback ,\nfor example [[5,1],[5,2]]\nfor this case our re will store 2, means i have to consider [5,2] transaction at last, \n\n\nTIME COMPLEXITY -O(N)\nSPACE COMPLEXITY - O(1)\n```\npublic long minimumMoney(int[][] transactions) {\n        \n        long res=0;\n        for(int arr[]:transactions){\n            res=Math.max(res, Math.min(arr[0],arr[1]));\n        }\n        for(int arr[]:transactions){\n            res+=Math.max(arr[0]-arr[1],0);\n        }\n        return res;\n    }\n```\n\n**Approach 3**\n\nTIME COMPLEXITY -O(N)\nSPACE COMPLEXITY - O(1)\n```\npublic long minimumMoney(int[][] transactions) {\n        \n        long res = 0, temp = 0;\n        for (int[] arr : transactions) {\n            temp = Math.max(temp, Math.min(arr[0], arr[1]));\n            res += Math.max(arr[0] - arr[1], 0);\n        }\n        return res + temp;\n    }\n```\n\t\n**Please Upvote the Post**
['Greedy', 'Sorting', 'Java']