Count inversions in an array efficiently

Q: Count inversions in an array efficiently

This is a Coding & Algorithms interview question from Akuna Capital for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given the array [5, 7, 9, 2, 3, 12, 8, 4], compute the number of inversion pairs (i, j) where i < j and arr[i] > arr[j]. Describe both a naive O(n^ 2) approach and an O(n log n) divide-and-conquer method, and analyze their complexities.

Count inversions in an array efficiently

Comments (0)