Count Of Smaller Numbers After Self

                                            
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> result(nums.size(), 0);
        vector<int> sorted;
        
        for(int i = nums.size() - 1; i >= 0; i--) {
            int left = 0, right = sorted.size();
            while(left < right) {
                int mid = left + (right - left) / 2;
                if(sorted[mid] >= nums[i]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            result[i] = right;
            sorted.insert(sorted.begin() + right, nums[i]);
        }
        
        return result;
    }
};

                                            
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>();
        List<Integer> sorted = new ArrayList<>();
        
        for (int i = nums.length - 1; i >= 0; i--) {
            int index = findIndex(sorted, nums[i]);
            result.add(0, index);
            sorted.add(index, nums[i]);
        }
        
        return result;
    }
    
    private int findIndex(List<Integer> list, int target) {
        if (list.isEmpty()) {
            return 0;
        }
        
        int left = 0;
        int right = list.size() - 1;
        
        if (target > list.get(right)) {
            return right + 1;
        }
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}

                                            
public class Solution {
    public IList<int> CountSmaller(int[] nums) {
        List<int> resultList = new List<int>();
        for (int i = 0; i < nums.Length; i++)
        {
            int count = 0;
            for (int j = i + 1; j < nums.Length; j++)
            {
                if (nums[j] < nums[i])
                {
                    count++;
                }
            }
            resultList.Add(count);
        }
        return resultList;
    }
}

                                            
function countSmaller(nums: number[]): number[] {
    const counts: number[] = new Array(nums.length).fill(0);
    
    const sortedNums = nums.slice().sort((a, b) => a - b);
    
    for (let i = 0; i < nums.length; i++) {
        const count = sortedNums.indexOf(nums[i]);
        counts[i] = count;
        sortedNums.splice(count, 1);
    }
    
    return counts;
};

To solve this coding challenge, you need a strategy to keep track of counts of smaller elements that appear to the right of each element in the input list. This problem involves a mix of sorting and searching techniques to achieve an efficient solution. The provided C++ solution uses an approach that merges the understanding of binary search and insertion into a sorted list. We will break it down into a detailed explanation and then provide pseudocode with comments.

Explanation

Problem Understanding :

Given an integer array
nums

, for each element at position
i

, you need to count how many elements to its right are smaller than itself.
The challenge is to achieve this efficiently, as a direct brute-force approach of nested loops would be too slow for large inputs.

Key Observations :

To determine the count of smaller elements to the right of each element, you can use a sorted list to keep track of the elements we have already processed (from right to left).
By inserting elements into the sorted list while maintaining its order, you can determine the position where the current element would fit. This position gives an indication of how many smaller elements are already in the list.

Detailed Steps :

Initialize an empty list
sorted_list

to keep elements in sorted order as we process them from right to left.
Initialize a
result

list to store the answer for each position.
For each element in the input list, starting from the last one:

Use a binary search to determine where to insert the current element in the sorted list. The position found will be the count of elements smaller than the current element.
Insert the element into the sorted list at the determined position.
Store the determined position in the result list.

Efficiency :

Using a sorted list with binary search and insertion enables the solution to run efficiently even for larger inputs.

Pseudocode

                                            
// Function to count smaller numbers after the given element in the array
function count_smaller_numbers_after_self(array nums) 
{
// Initialize a result list with zeros, which has the same length as nums
list result = create_list_with_zeros(length_of(nums))

// Initialize an empty list to keep track of the numbers in sorted order
list sorted_list = create_empty_list()

// Iterate through nums from the end to the start
for index from length_of(nums) - 1 down to 0 
{
// Initialize two pointers for binary search
left_pointer = 0 
right_pointer = length_of(sorted_list)

// Binary search to find the correct position to insert nums[index]
while left_pointer < right_pointer 
{
middle_pointer = left_pointer + (right_pointer - left_pointer) / 2
if sorted_list[middle_pointer] >= nums[index]
right_pointer = middle_pointer
else 
left_pointer = middle_pointer + 1
}

// The correct position found indicates how many elements are smaller
result[index] = right_pointer

// Insert the element into the sorted_list at the found position
insert(sorted_list, right_pointer, nums[index])
}

// Return the result list
return result
}

Detailed Steps in Pseudocode

Initialize Result List :

Create a list
result

initialized with zeros, which will store the count of smaller numbers for each element in
nums

.

Initialize Sorted List :

An empty list
sorted_list

is initialized to maintain the elements we have processed in sorted order.

Iterate from End to Start :

Loop through each index from the end of
nums

to the start.
For each element, initialize pointers
left

and
right

to perform binary search.

Binary Search :

Perform a binary search on
sorted_list

to find the correct position to insert the current element
nums[i]

. The right pointer at the end of the binary search gives the count of numbers smaller than
nums[i]

.

Store Count in Result :

Store the right pointer value (the count of smaller elements) in
result[i]

.

Insert Element :

Insert
nums[i]

into
sorted_list

at the position given by the binary search.

Return Result :

The result list now contains the desired counts of smaller elements for each position in the input list.

By following this outline of steps, the solution is both conceptually clear and efficiently executed.