Dip Explained with Pictures || C++ Code || Easy to Understand
A short question summary:\n\nWe are given some transaction as [cost, cashback].\nWe need to have atleast cost amount of money to proceed with the transaction af
A short question summary:\n\nWe are given some **transaction as [cost, cashback]**.\nWe need to have **atleast cost amount of money** to proceed with the transaction after which our **new money is old_money - cost + cashback**.\n\nWe need to return min money required such that no matter how the transactions are arranged, we can complete all transactions.\n\n**Intuition:**\n\nIf we can somehow get the worst possible permuation of the transactions then we can get our answer easily either by just traversing the permutation or by doing binary search over answer.\n\n**Let\'s Understand Dip now**\n\nAssume I have a perumation of orders as:\n[6,4] \u2014> [10,2] \u2014> [1,6] \u2014> [5,11] \u2014> [3,1]\nwhere first element is cost and second element is cashback.\n\nNow let\'s assume we have currMoney as 0.\n\nSo if we proceed with first transaction our currMoney will be -6.\n(Just don\'t think about the condition that we will need atleast cost money, you will understand it later)\n\nAnd if we go to second transation firt we add cashback of last transaction to i.e. +4 and then I incur the cost of next transaction i.e. -10.\n\nSo if we plot a graph of currMoney over all transactions, it will be like this:\n![image](https://assets.leetcode.com/users/images/491154ee-45fa-4ac1-b2b6-fa3a3aa04df5_1663485485.5813172.png)\nWhat\'s the most negative value we have in this graph?\nIts -12\nand That is minimum dip.\nAnd also 12 is the min amount required if we want to complete all transaction.\n(Now think about that condition which I said don\'t think about :) )\n\nTake 12 and do the transaction on the permuations given above, you will understand better.\n\nNow I hope the concept of dip is clear\n\n**But how it is useful?**\n\nIt is useful in sorting the array, so that we can get the worst permuation.\n\nSo basically we have to arrange transactions in such a way that we get the least Min Dip possible across all of it\'s permuatations.\n\nConsider only 2 transactions:\n[6,7] and [5,11]\n\nNow either our arrange can be [6,7] \u2014> [5,11] or it can be [5,11] \u2014> [6,7].\n\nNow see their graph:\n![image](https://assets.leetcode.com/users/images/ed06f8b2-0d5b-4361-aa4d-c363105010f6_1663486118.816935.png)\nAs you can see that [6,7] --> [5,11] is giving us a better min dip of -6 instead of -5 of another option.\n\nThat\'s how we have to sort the array.\n\nIn our comparator or Lambda function, wichever you used for sorting, we have two transactions.\n\nLet\'s say transaction a and b.\n\nWe have to check whether a-->b is giving a better min dip or b-->a and then according to that we have to return true or false.\n\nHow to calculate dip?\n\nFor transaction of a-->b, there will be two dips:\nFirst dip = -a[cost]\nSecond dip = -a[cost] + a[cashback] - b[cost]\n\n(If you didn\'t get this then think how lines are flowing in the graph where two permuations were compared. It first goes down, then goes up and then again down. We are calculating those two down points)\n\nIf both have same dip, then prefer the transaction which have higher cost.\n\nFor **Code explanation** you can checkout the video I attached at the bottom of this post.\n\nC++ Code for Binary Search over answer:\n```\nclass Solution {\npublic:\n\n\tbool isPossible(long long currMoney, vector<vector<int>>& transactions)\n\t{\n\t\tfor (vector<int>& t : transactions)\n\t\t{\n\t\t\tif (currMoney < t[0])\n\t\t\t\treturn false;\n\t\t\tcurrMoney += -t[0] + t[1];\n\t\t}\n\t\treturn true;\n\t}\n\n\tlong long minimumMoney(vector<vector<int>>& transactions) {\n\t\tint opt1,opt2;\n        sort(begin(transactions), end(transactions),\n\t\t     [&](vector<int>& a, vector<int>& b)\n\t\t{\n\t\t\topt1 = min(-a[0], -a[0] + a[1] - b[0]); //a->b\n\t\t\topt2 = min(-b[0], -b[0] + b[1] - a[0]); //b->a\n\t\t\tif (opt1 != opt2)\n\t\t\t\treturn opt1 < opt2;\n\t\t\treturn a[0] > b[0];\n\t\t});\n\t\tlong long left = 0;\n\t\tlong long right = LLONG_MAX;\n\t\tlong long ans, mid;\n\t\twhile (left <= right)\n\t\t{\n\t\t\tmid = left + (right - left) / 2;\n\t\t\tif (isPossible(mid, transactions))\n\t\t\t{\n\t\t\t\tans = mid;\n\t\t\t\tright = mid - 1;\n\t\t\t}\n\t\t\telse\n\t\t\t\tleft = mid + 1;\n\t\t}\n\t\treturn ans;\n\t}\n};\n```\n\nC++ Code for optimised approach(Just get Min dip and return absolute of it):\n```\nclass Solution {\npublic:\n\tlong long minimumMoney(vector<vector<int>>& transactions) {\n\t\tint opt1, opt2;\n\t\tsort(begin(transactions), end(transactions),\n\t\t     [&](vector<int>& a, vector<int>& b)\n\t\t{\n\t\t\topt1 = min(-a[0], -a[0] + a[1] - b[0]); //a->b\n\t\t\topt2 = min(-b[0], -b[0] + b[1] - a[0]); //b->a\n\t\t\tif (opt1 != opt2)\n\t\t\t\treturn opt1 < opt2;\n\t\t\treturn a[0] > b[0];\n\t\t});\n\t\tlong long currMoney = 0;\n\t\tlong long ans = 0;\n\t\tfor (vector<int>& currTaransaction : transactions)\n\t\t{\n\t\t\tcurrMoney -= currTaransaction[0];\n\t\t\tans = min(ans, currMoney);\n\t\t\tcurrMoney += currTaransaction[1];\n\t\t}\n\t\treturn abs(ans);\n\t}\n};\n```\nTime Complexity - O(nlogn) (sorting)\nSpace Comlexity - O(1)\n\nFor Code Explanation check this video:\n<iframe width="560" height="315" src="https://www.youtube.com/embed/nXAVgtjvkfc?start=939" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>\n\n**If you liked the post then please upvote, it will motivate me to write more of such posts for hard problems.**
['Greedy', 'C', 'Sorting', 'Binary Tree']