PreviousNext
Coding/Searching and sorting

Significant inversions

Write codeHard30 minCitadel and Google style

Your task

Count the number of 'significant' inversions in an array: pairs of indices (i, j) with i < j such that nums[i] > 2 * nums[j]. The array has up to 10^5 elements and values may be negative and fit in 32-bit ints. An O(n^2) double loop is too slow; use a modified merge sort. Return the count.

Examples

count_significant_inversions(nums: list[int]) -> int
Example 1
Inputcount_significant_inversions([1, 3, 2, 3, 1])
Output2