Dear community,

I hope you all are doing good and safe. I just want to know one thing. Recently I had a interview and the interviewer asked one question, how to solve inversion count problem.

I suggested two approaches to him (1. brute force, and 2. using merge sort). He was completely satisfied by my both the approaches.

But at last, he asked one question to me. Can we solve inversion count problem in O(n+k) where n <= k <= (n*n) ?

I couldn't suggest such approach to him. Also, my bad luck, I couldn't ask him about such approach. But, I am just curious to know is this really possible ? Can someone suggest some approach which could solve inversion count problem in O(n+k) where n <= k <= (n*n) ?

Thanks.