16. Count Inversions in an Array

Given an array, count the number of pairs (i, j) with i < j and arr[i] > arr[j]. Print that count.

Input: The first line contains an integer n. The second line contains n space-separated integers. Output: Print a single integer - the number of inversions (pairs i < j with arr[i] > arr[j]).

1 <= n <= 10^5

This problem is a great example of getting a seemingly unrelated count 'for free' by carefully instrumenting an existing, well-known algorithm (merge sort) rather than designing something new from scratch.

Count how many pairs of numbers in an array are 'out of order' relative to each other - meaning an earlier number is bigger than a later one. Brute force: Directly compare every pair of positions (i, j with i < j) and count how many have arr[i] > arr[j] - this works correctly but costs O(n²), too slow for large arrays. Optimised: A modified merge sort counts inversions 'for free' as a byproduct of the normal merging process - every time the merge step takes an element from the right half while left-half elements STILL remain unmerged, ALL of those remaining left-half elements are inversions with it (since the left half is already sorted internally), letting you count many inversions in a single accounting step instead of one comparison at a time.

Compress the array values to ranks 1..n (since only relative order matters), then sweep the array from right to left, maintaining a Binary Indexed Tree over the compressed ranks. For each element, query the BIT for how many smaller elements have already been inserted (this count is exactly the number of inversions formed with elements to its right... equivalently sweep left to right and query counts of larger already-inserted ranks), then insert the current rank into the BIT. Each query/update is O(log n), so the whole pass is O(n log n) instead of the brute force's O(n^2), at the cost of building an explicit tree structure and a compression step. Time: O(n log n) Space: O(n)

Run merge sort on the array, and during the merge step of each recursive call, count cross-inversions: whenever an element from the right half is placed into the merged output ahead of remaining elements from the left half, every one of those remaining left-half elements forms an inversion with it, so add the count of remaining left-half elements in one shot. Summing these counts across all merge steps gives the total inversion count in the same O(n log n) time as sorting itself. This achieves the same asymptotic bound as the Fenwick tree approach but needs no compression step or extra tree structure, just the standard merge routine, making it the simplest and most direct optimal solution. Time: O(n log n) Space: O(n)

Check every pair of indices (i, j) with i < j directly using two nested loops, and increment a counter whenever arr[i] > arr[j]. This directly implements the definition of an inversion with no auxiliary data structures, so it is trivial to get right, but it examines every one of the O(n^2) pairs even though most of that information could be reused across comparisons. Time: O(n^2) Space: O(1)

1. Think of this as a variant of merge sort: split the array into two halves and recursively count inversions within each half. 2. While MERGING the two already-sorted halves back together, count how many cross-half inversions exist - specifically, every time you take an element from the right half BEFORE some remaining elements in the left half, those remaining left-half elements are all bigger than it (since the left half is sorted), so they ALL form an inversion with it at once. 3. Add up the inversions found within the left half, within the right half, and across the merge step.

Time: O(n log n) - the same complexity as merge sort itself, since inversion-counting is just extra bookkeeping added during the normal merge step. Space: O(n), for the temporary arrays merge sort itself already needs.

n = 1 (no pairs, answer 0); an already ascending-sorted array (0 inversions) versus a strictly descending one (the maximum possible count); and n = 10^5 (largest, confirming the O(n log n) merge-sort approach is needed).

Be ready to explain precisely HOW the merge step reveals inversions in bulk (not one comparison at a time) - this insight, not just 'use merge sort', is what interviewers are really checking for.