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.
Yes, it’s kinda similar to the bubble sort. At each step add element to the end of the array and move it to the left until it will end at the good position.
That has a name and it's insertion sort.
If $$$k = n \cdot n$$$, isn't it the same as the bruteforce bubble sort approach?