You are given an array of transactions transactions where transactions[i] = [fromi, toi, amounti] indicates that the person with ID = fromi gave amounti $ to the person with ID = toi.

Return the minimum number of transactions required to settle the debt.

The question below is similar to an N way partition problem (instead of 3 way partition problem

Then the problem can be converted to the following:

  • Given N accounts/persons who have non zero amounts,
  • find the M = max number of sets where each set s has sum(s)==0.
  • Each of these sets must be min_set. In other words, min_set CANNOT be divided to setA and setB where sum(setA) == sum(setB)==0.

--

--

I am adding a few problems pertaining to the use of this data structure

Next greater element

Points to remember:

  1. We need to process the array from right to left
  2. Using stack we end up processing each element just 2 times , hence the complexity is just O(n)
void nextgreaterelement()

--

--

Merge Sort (Count Inversions)

Complexity : Worst Case O(n log n)

Quick Sort

Complexity : Worst Case O(n²)

int partition(int l,int r,vector<int>&v){int pivot=(l+r)/2;while(l<=r){    while(v[l]<v[pivot])    l++;    while(v[r]>v[pivot])     r--;    if(l<=r)    {       swap(v[l],v[r]);       l++;        r--;     }}return l;}void quicksort(int l,int r,vector<int>&v){   int idx=partition(l,r,v);   if(l<idx-1)     quicksort(l,idx-1,v);   if(idx<r)     quicksort(idx,r,v);}void quick(){   vector<int>v;   v.push_back(10);   v.push_back(20);   v.push_back(9);   v.push_back(3);   v.push_back(4);   quicksort(0,v.size()-1,v);   for(int i=0;i<v.size();i++)    cout<<v[i]<<" ";   cout<<endl;}

Points to remember:

  • How do you make the partition algorithm more efficient
  • Applications ? (kth largest element, getting k top elements etc. )

--

--