Skip to content
Katabench
Try free

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, and
  • nums[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 performance bar

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

C#
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.

C# coding challenges →

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