“Count of the smaller number after self (CSNAS)” is a Algorithms Problem in LeetCode. It is considered as a Hard issue but can be solved by Merge Sort algorithm in an efficient way. In my project, I encounter a problem which is quite similar to problem CSNAS, and I call it as Weighted Count of the Smaller Number After Self (WCSNAS) problem. Before introducing the WCSNAS problem and related efficient solution, we first describe the CSNAS in the following.
- 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
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
- You are given two arrays, the first array is an integer array nums and the second array is a double array weight. You have to return a new _weight_counts_ array. The counts array has the property where
wcounts[i]is the summation of weights of smaller elements to the right of
nums = [1, 3, 5, 4, 2, 2]
weight = [3.0, 2.0, 4.0, 1.0, 2.0, 5.0]
wcounts = [0.0, 7.0, 8.0, 7.0, 5.0, 0.0]
To the right of 1 there are 0 smaller element.
To the right of 3 there are 2 smaller elements (2 and 2) and their related weights are 2.0 and 5.0. Therefore, the summation of weights is 7.0.
To the right of 5 there are 3 smaller elements (4, 2, and 2) and their related weights are 1.0, 2.0 and 5.0. Therefore, the summation of weights is 8.0.
StefanPochmann suggest a merge sort
solution for CSNAS with merge sort: “The smaller numbers on the right of a number are exactly those that jump from its right to its left during a stable sort. So I do mergesort with added tracking of those right-to-left jumps.”
My solution mimic the solution of CSNAS by adding tracking of those right-to-left jumps for weight array. The source code implemented in C++ is shown below.