brute-force for the last index that gives minimum money.
Intuition\n Describe your first thoughts on how to solve this problem. \nLet\'s define sum[i] = \u03A3_k=[0:i] ( -cost[k] + cashback[j] ).\n\nFor a given permut
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet\'s define sum[i] = \u03A3_k=[0:i] ( -cost[k] + cashback[j] ).\n\nFor a given permutation of transactions, the additional money needed is the minimum value of sum[i] (multiplied by -1; if this value is non-negative, no additional money is needed). We calculate this for all possible permutation of transaction , and the answer is the minimum value (= MIN ). \n\nSuppose sum[i] = MIN for a particular permutation. In this case, there are no elements j < i where -cost[j] + cashback[j] > 0. This is because if such an element exists, conducting the jth transaction after the ith one would reduce the money, contradicting the assumption that sum[i] is the minimum value (MIN).\n\nWith this consideration, sum[i] = (sum of j where -cost[j] + cashback[j] < 0 for j < i) + (-cost[i]).  it can be calculated efficiently by precomputing total money of -cost[j] + cashback[j].\n\n\nI don\'t understand the solution involving sorting in Hint.teach me please.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\ntypedef long long ll;\nclass Solution {\npublic:\n    long long minimumMoney(vector<vector<int>>& t) {\n        vector<ll>minus,plus;\n        int n=t.size();\n        ll mn=0,sum=0;\n        for(int i=0;i<n;i++){\n            if(-t[i][0]+t[i][1]<0){\n                sum=sum-t[i][0]+t[i][1];\n                minus.push_back(i);\n            }else{\n                plus.push_back(i);\n            }\n        }\n        for(int i:minus){\n            ll cur=sum+t[i][0]-t[i][1];\n            mn=min(mn,cur-t[i][0]);\n        }\n        for(int i:plus){\n            mn=min(mn,sum-t[i][0]);\n        }\n        return -mn;\n    }\n};\n```
['C++']