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:

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

void nextgreaterelement(){vector<int>v;stack<int>st;v.push_back(2);v.push_back(1);v.push_back(2);v.push_back(4);v.push_back(3);vector<int>result;result.resize(v.size(),-1);for(int i=v.size()-1;i>=0;i--){ while(!st.empty()&&st.top()<=v[i]) { st.pop(); } if(!st.empty()) result[i]=st.top(); st.push(v[i]);}for(int i=0;i<result.size();i++)cout<<result[i]<<" ";}

**References:**

Problems

1.https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/ — why does the heuristic in bfs / the condition to enter into the bfs queue matter ?

**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. )