Problem Submissions Solution
Count Inversions
Difficulty: Medium
Acceptance: 16.93%
Points: 30.00
Given an array of integers **arr[]**. Find the **Inversion Count** in the array. Two elements arr[i] and arr[j] form an inversion if **arr[i] > arr[j]** and **i < j**. **Inversion Count:** For an array, inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted then the inversion count is 0. If an array is sorted in the reverse order then the inversion count is the maximum.
Examples:
Expected Time Complexity: O(n log n)
Expected Space Complexity: O(n)
Constraints:
- 1 <= arr.size() <= 10^5
- 1 <= arr[i] <= 10^4
Companies:
Amazon Microsoft Adobe Flipkart Myntra
Topics:
Array Sorting Algorithms
