Count number of previous elements greater than its element at present index

Question

Suppose I have a vector containing n elements. I want to find out the number of previous elements greater than its element at present index i. I want to find A[i] > A[j] && i < j for all elements of the vector.

Constraints:

1 <= t <= 1000
1 <= n <= 10^5
1 <= A[i] <=10^5

My code:

#include<bits/stdc++.h>
using namespace std;
int main() {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 int t;
 cin >> t;
 while(t--) {
 int n,a,i,j;
 cin >> n;
 vector<int>v1;
 for(i=0;i<n;i++) {
 cin >> a;
 v1.push_back(a);
 }
 int cnt=0,sum=0;
 for(i=0;i<n;i++) {
 if( i!=0) {
 for(j=0;j<i;j++) {
 if(v1[i]<v1[j]) {
 cnt++;
 }
 }
 }
 // cout << cnt << " ";
 sum=sum+cnt;
 cnt=0;
 }
 cout << sum << '\n';
 }
}

This code is running fine for all the test cases except only one. It is showing the Time limit exceeded for one of the test cases. Can anyone help me?

• user673679: What are t and n?

Answer 1

I don't think there is a logic error in what you have posted. And even though there are details that would make it nicer (the cycle can for example run from i=1, questionable use of bits/stdc++.h header, long variable scopes and similar), it should do its job.

I suggest to think about time complexity of the algorithm. Your brute force approach will have quadratic complexity and may be too slow when the input is large.

There are different approaches that you can try. For example, I see you tagged your post with binary-search tag. Why? You could for example keep your vector sorted as the user enters the values. When adding a new number, find where it belongs (you can do it by bisection - with logarithmic complexity). All numbers to the left are smaller, the ones on the right are larger. Then insert the number and repeat. How to do it exactly is up to you, if you're allowed to use C++ algorithms, std::lower_bound and std::vector::insert will do the hard work for you.

You can of course craft some tree structure of your own to do something along those lines.