Count of Smaller Numbers After Self

class Counter {
public:
    vector<int> countElements(vector<int>& elements) {
        int size = elements.size();
        vector<int> counts(size);
        vector<int> positions(size);
        for (int k = 0; k < size; k++) {
            positions[k] = k;
        }
        divisionSort(positions, 0, size, counts, elements);
        return counts;
    }

    void divisionSort(vector<int>& positions, int start, int end, vector<int>& counts,
                      vector<int>& elements) {
        if (end - start <= 1) {
            return;
        }
        int divide = (start + end) / 2;
        divisionSort(positions, start, divide, counts, elements);
        divisionSort(positions, divide, end, counts, elements);
        combine(positions, start, end, divide, counts, elements);
    }

    void combine(vector<int>& positions, int start, int end, int divide, vector<int>& counts,
                 vector<int>& elements) {
        int leftIdx = start;
        int rightIdx = divide;
        vector<int> sortedTemp;
        
        while (leftIdx < divide && rightIdx < end) {
            if (elements[positions[leftIdx]] <= elements[positions[rightIdx]]) {
                counts[positions[leftIdx]] += rightIdx - divide;
                sortedTemp.push_back(positions[leftIdx]);
                leftIdx++;
            } else {
                sortedTemp.push_back(positions[rightIdx]);
                rightIdx++;
            }
        }

        while (leftIdx < divide) {
            counts[positions[leftIdx]] += rightIdx - divide;
            sortedTemp.push_back(positions[leftIdx]);
            leftIdx++;
        }

        while (rightIdx < end) {
            sortedTemp.push_back(positions[rightIdx]);
            rightIdx++;
        }

        move(sortedTemp.begin(), sortedTemp.end(), positions.begin() + start);
    }
};

The provided C++ code implements a "Count of Smaller Numbers After Self" solution using a modified merge sort algorithm. The code primarily revolves around calculating how many numbers are smaller than the current number to its right. This solution involves a class Counter with three main methods:

• countElements: initializes data structures and begins the sort and merge process.
• divisionSort: recursively divides arrays into smaller segments until they are individual elements.
• combine: merges the segments back together while counting the number of smaller numbers.

Here are the detailed actions taken during execution:

1. countElements initializes a vector counts to store the result and a vector positions to act as an index array for the elements. It then calls divisionSort which begins the recursive sorting and merging process.

2. divisionSort is a recursive function that splits the array into two halves until each segment is a single element. After splitting, it calls itself for the left and right halves, and then calls combine to merge those halves.

3. In the combine function, two pointers (leftIdx and rightIdx) track the current indices of the left and right halves. As it progresses through the halves, the function compares elements and counts how many elements from the right half are smaller than those in the left half. This count is updated in the counts vector. The array is then recombined in sorted order using these indices.

The primary data structures used are:

• elements: the input vector of integers.
• counts: contains the result of how many elements are smaller after each element in elements.
• positions: an auxiliary array used to track the original indices of elements during the sorting process, which is crucial for updating the counts correctly.

This approach, using a divide and conquer strategy, optimizes the process of counting smaller numbers after each element and leverages efficient sorting mechanics provided by merge sort. It manages both the sorting of the array and the essential counting process simultaneously, ensuring each step contributes directly to the final result.

class Solution {
    public List<Integer> findSmallerCounts(int[] values) {
        int length = values.length;
        int[] counts = new int[length];
        int[] position = new int[length];
        for (int i = 0; i < length; i++) {
            position[i] = i;
        }
        divideAndConquer(position, 0, length, counts, values);
        
        List<Integer> finalCounts = new ArrayList<Integer>(length);
        for (int count : counts) {
            finalCounts.add(count);
        }
        return finalCounts;
    }

    private void divideAndConquer(int[] position, int start, int end, int[] counts, int[] values) {
        if (end - start <= 1) {
            return;
        }
        int half = (start + end) / 2;
        divideAndConquer(position, start, half, counts, values);
        divideAndConquer(position, half, end, counts, values);
        combine(position, start, end, half, counts, values);
    }

    private void combine(int[] position, int start, int end, int half, int[] counts, int[] values) {
        int leftIndex = start, rightIndex = half; 
        List<Integer> sortedTemp = new ArrayList<Integer>(end - start);
        while (leftIndex < half && rightIndex < end) {
            if (values[position[leftIndex]] <= values[position[rightIndex]]) {
                counts[position[leftIndex]] += rightIndex - half;
                sortedTemp.add(position[leftIndex]);
                leftIndex++;
            } else {
                sortedTemp.add(position[rightIndex]);
                rightIndex++;
            }
        }
        while (leftIndex < half) {
            counts[position[leftIndex]] += rightIndex - half;
            sortedTemp.add(position[leftIndex]);
            leftIndex++;
        }
        while (rightIndex < end) {
            sortedTemp.add(position[rightIndex]);
            rightIndex++;
        }
        for (int i = start; i < end; i++) {
            position[i] = sortedTemp.get(i - start);
        }
    }
}

The provided Java solution is constructed to address the problem of computing the count of elements smaller than each element given a sequence of values. The approach involves a combination of divide and conquer strategy along with merging processes applied efficiently to traverse and compute the necessary counts.

• Initialization of Variables: The solution begins by initializing necessary arrays and indexes. A primary array, values, holds the integers we need to analyze. Associated with it are counts to store results, and position which tracks the index of each element primarily used during merging to compute the smaller elements count accurately.

• Divide and Conquer Approach: The function divideAndConquer recursively splits the index array position into smaller subarrays until subarrays of size one or empty are reached. The recursion involves splitting tasks into two halves until further division is not possible.

• Combining and Merging: During the merge phase, the indices are evaluated to count the number of elements less than the current element in the other half of the divided array. The combine function is pivotal in merging the divided parts by sorting them and updating counts based on how many elements from the right half are smaller than elements in the left half during the merge.

• Output Processing: Post-processing, the result counts is transferred to a list, finalCounts to match the expected output structure.

The essential part of this process is the combined use of indices kept in the position array, which allows the method to efficiently count and accumulate the results based on the relative position of elements during the merge phase. By leveraging array indices and counting directly during the merge step, the solution avoids a separate pass to count smaller elements, thus optimizing overall execution time for large input sizes. This structure ensures the method remains efficient and effective for the problem's constraints and requirements.

class Solution:
    def countSmallerElements(self, nums: List[int]) -> List[int]:
        length = len(nums)
        array = [[value, index] for index, value in enumerate(nums)]
        counts = [0] * length

        def sort_and_count(array, start, end):
            if end - start <= 1:
                return
            middle = (start + end) // 2
            sort_and_count(array, start, middle)
            sort_and_count(array, middle, end)
            merge_and_count(array, start, end, middle)

        def merge_and_count(array, start, end, middle):
            p1 = start
            p2 = middle
            sorted_temp = []
            while p1 < middle and p2 < end:
                if array[p1][0] <= array[p2][0]:
                    counts[array[p1][1]] += p2 - middle
                    sorted_temp.append(array[p1])
                    p1 += 1
                else:
                    sorted_temp.append(array[p2])
                    p2 += 1
            while p1 < middle:
                counts[array[p1][1]] += p2 - middle
                sorted_temp.append(array[p1])
                p1 += 1
            while p2 < end:
                sorted_temp.append(array[p2])
                p2 += 1
            for i in range(start, end):
                array[i] = sorted_temp[i - start]

        sort_and_count(array, 0, length)

        return counts

This Python solution tackles the problem of counting the number of smaller numbers after each element in a given list. The implementation employs a merge sort technique to sort an input list while simultaneously counting the smaller elements. Below are the key components and their functions:

• Array creation that pairs each element in nums with its original index.
• A function sort_and_count follows the divide part of the merge sort, which recursively splits the list into halves.
• A merge function merge_and_count that not only merges two halves but also counts the number of smaller elements using the indices stored in the array.

During merging, for each element from the left half of the split, you count how many elements in the right half are smaller and update the count at the original index of the element in counts.

The steps to achieve this are:

1. Transform the original nums list into an array of tuples, where each tuple contains the number and its original index.
2. Define a recursive function to split the array into halves until single elements or empty lists are reached.
3. Implement the merge function, where for each element in the left half being merged back, determine how many elements in the right half are smaller, using the indices to keep the count for the correct element.
4. Update the original list segment with merged results.

The final output is a list counts that contains the count of smaller elements after each original element in the input list nums.