Count of Smaller Numbers after Self | Number of Swaps to Sort | Algorithm Swap
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Input:
[5,2,6,1]Output:
[2,1,1,0]Explanation:
For the number 5, there are 2 numbers smaller than it after it. (2 and 1)
For the number 2, there is 1 number smaller than it after it. (1)
For the number 6, there is also 1 number smaller than it after it. (1)
For the number 1, there are no numbers smaller than it after it.
Hence, we have [2, 1, 1, 0].
Number of swaps to sort
Another way to phrase the question is:
If we sort the array by finding the smallest pair i, j where i < j and a[i] > a[j] how many swaps are needed?
To answer that question we just have to sum up the numbers in the above output array: 2 + 1 + 1 = 5 swaps.
Try it yourself
Title
Script
Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.
Contrary to popular belief, Lorem Ipsum is not simply random text.
>>> a = [1, 2, 3]
>>> a[-1]
3