Count Inversions
Hard About 35 min Free, no account needed
Count every out-of-order pair without examining every pair.
The brief
An inversion is a pair of indices (i, j) where:
i < j, andnums[i] > nums[j].
Return the total number of inversions in nums.
Equal values do not form an inversion. Values may be negative, and the answer can
be larger than a 32-bit integer. Treat nums as read-only and do not mutate it.
The obvious solution checks every pair with two nested loops. That approach is honest and correct, but it takes O(n²) time. The hidden tests include 200,000 values in descending and shuffled orders, forcing billions of pair checks across different input shapes. Find an O(n log n) approach instead.
Starter code
using System;
public class Solution
{
// TODO: count pairs (i, j) where i < j and nums[i] > nums[j].
public long CountInversions(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
Related guides
What it practices
- Divide and conquer
- Split the input, solve the halves, and count or combine across the split, as merge sort does.
Related katas
- Count Bounded Range Sums Hard Free Count signed subarray totals inside an inclusive band without enumerating quadratic pairs.
- Edit Distance Hard Free Fewest single-character edits turning one word into another.
- Fewest Cache Fetches Hard Free Use tomorrow's requests to find the smallest possible number of cache misses today.
- First Missing Positive Hard Free Find the smallest positive integer that does not appear in the array.