# Evolve from brute force to optimal, a review of all solutions

• This is similar to Count of Smaller Numbers After Self. Solutions are very similar.

1. O(n^2) brute force
``````    int reversePairs(vector<int>& nums) {
int n = nums.size(), res=0;
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(nums[i]/2.0>nums[j]) res++;
return res;
}
``````
1. O(n^2) Brute force with binary search.
``````    int reversePairs(vector<int>& nums) {
int n = nums.size(), res=0;
if(!n) return 0;
vector<int> vstd(1,nums.back());
for(int i=n-2;i>=0;i--) {
res += lower_bound(vstd.begin(),vstd.end(),(double)nums[i]/2) - vstd.begin();
vstd.insert(lower_bound(vstd.begin(),vstd.end(),nums[i]), nums[i]);
}
return res;
}
``````
1. Average O(nlogn), worst O(n^2) binary search tree.
``````    class Node {
public:
Node (int val):val_(val),left_(NULL),right_(NULL),lt_(0){}
Node *left_,*right_;
int lt_,val_;
};
void insert(int val, Node *rt) {
Node **r = &rt;
while(*r)
if(val<(*r)->val_) {
(*r)->lt_++;
r=&(*r)->left_;
} else r=&(*r)->right_;
*r= new Node(val);
}
int countSmaller(double val, Node* r) {
int ct = 0;
while(r)
if(val<r->val_) r = r->left_;
else {
ct += r->lt_+(val>r->val_);
r=r->right_;
}
return ct;
}
void dlt(Node *r) {
if(!r) return;
dlt(r->left_);
dlt(r->right_);
delete r;
}
int reversePairs(vector<int>& nums) {
if(nums.empty()) return 0;
int n=nums.size(), res=0;
Node *r=new Node(nums.back());
for(int i=n-2;i>=0;i--) {
res+=countSmaller(nums[i]/2.0,r);
insert(nums[i],r);
}
dlt(r);
return res;
}
``````
1. O(nlogn) binary index tree.
``````    int reversePairs(vector<int>& nums) {
vector<int> sorted=nums;
sort(sorted.begin(),sorted.end());
int n = nums.size(), res = 0;
vector<int> bit(n+1);
unordered_map<int,int> index;
for(int i=0;i<n;i++) index[sorted[i]]=i+1;
for(int i=n-1;i>=0;i--) {
res+=getSum(lower_bound(sorted.begin(),sorted.end(),nums[i]/2.0)-sorted.begin(),bit);
update(index[nums[i]],bit);
}
return res;
}
int getSum(int i, vector<int>& bit) {
int sum = 0;
while(i) {
sum+=bit[i];
i&=i-1;
}
return sum;
}
void update(int i, vector<int>& bit) {
while(i<bit.size()) {
bit[i]++;
i+=i&-i;
}
}
``````
1. O(nlogn) merge sort.
``````    int reversePairs(vector<int>& nums) {
return mergeSort(0,nums.size()-1,nums);
}
int mergeSort(int l, int r, vector<int>& nums) {
if(l>=r) return 0;
int mid=(r-l)/2+l, count = mergeSort(l,mid,nums) + mergeSort(mid+1,r,nums);
for(int i=l,j=mid+1;i<=mid;i++) {
while(j<=r && nums[i]/2.0>nums[j]) j++;
count+=j-mid-1;
}
int i=l,j=mid+1,k=0;
vector<int> merge(r-l+1);
while(i<=mid || j<=r)
if(j>r || (i<=mid && nums[i]<=nums[j])) merge[k++]=nums[i++];
else merge[k++]=nums[j++];
copy(merge.begin(),merge.end(),nums.begin()+l);
return count;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.