Count of Smaller Numbers after Self | Number of Swaps to Sort | Algorithm Swap
Given an integer array nums, return an array counts where counts[i] is the number of elements to the right of index i that are smaller than nums[i].
Example
Input: [5,2,6,1]
Output: [2,1,1,0]
At index 0, value 5 has two smaller values on its right (2 and 1), so counts[0] = 2. At index 1, value 2 has one smaller value on its right (1), so counts[1] = 1. At index 2, value 6 has one smaller value on its right (1), so counts[2] = 1. At index 3, value 1 has no elements on its right, so counts[3] = 0.
Number of swaps to sort
A closely related question asks: if we repeatedly fix inversions, how many swaps are needed to sort the array? Each inversion is a pair (i, j) with i < j and nums[i] > nums[j].
The total number of swaps equals the total number of inversions. In this problem, each counts[i] tells you how many inversions start at index i, so summing the counts array gives the total inversion count. For [5,2,6,1], that sum is 2 + 1 + 1 + 0 = 4.