Q) Given an array A1, A2 ... AN and K count how many subarrays have inversion count greater than or equal to K. N <= 10^5 K <= N*(N-1)/2
So, this question I came across in an interview. I came up with the naive solution of forming all subarrays with two for loops (O(n^2) ) and counting inversions in the array using modified merge sort which is O(nlogn). This leads to a complexity of O(n^3logn) which I guess can be improved. Any leads how I can improve it? Thanks!
You can solve it in O(nlogn) if I'm not wrong, using two moving pointers.
Start with the left pointer in the first element and move the right pointer until you have a subarray with >= K inversions. To do that, you can use any balanced binary search tree and every time you move the pointer to the right, count how many elements bigger than this one are already in the tree. Then you insert the element in the tree too.
When you hit the point in which you already have >= K inversions, you know that every longer subarray with the same starting element also satisfies the restriction, so you can add them all.
Then move the left pointer one position to the right and subtract the inversions of it (again, look in the tree for elements smaller than it). Now you can do the same as before again.
An amortized analysis easily shows that this is O(nlogn), as the two pointers only traverse once the array and each operation in the tree is O(logn).
