315. Count of Smaller Numbers After Self – Leetcode Solutions

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
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.

Example 2:

Input: nums = [-1]
Output: [0]

Example 3:

Input: nums = [-1,-1]
Output: [0,0]

from bisect import bisect_left

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        # Result array to store the counts
        result = []
        # Sorted list to maintain elements as we process them in reverse order
        sorted_list = []
        
        # Traverse the input array from right to left
        for num in reversed(nums):
            # Find the position in the sorted_list where this number would fit
            position = bisect_left(sorted_list, num)
            
            # The position gives us the count of smaller elements
            result.append(position)
            
            # Insert the current number into the sorted list at the correct position
            sorted_list.insert(position, num)
        
        # Since we filled the result in reverse order, reverse it before returning
        return result[::-1]

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        // Result vector to store the counts of smaller elements for each index
        vector<int> result;
        
        // A sorted vector that we will use to maintain the elements we have processed
        vector<int> sorted_list;
        
        // Traverse the array from right to left
        for (int i = nums.size() - 1; i >= 0; --i) {
            // Use lower_bound to find the insertion point in the sorted list
            // lower_bound returns an iterator to the first element that is not less than nums[i]
            auto it = lower_bound(sorted_list.begin(), sorted_list.end(), nums[i]);
            
            // The position (distance from the start of the sorted list) gives the count of smaller elements
            int count = it - sorted_list.begin();
            result.push_back(count);
            
            // Insert the current number into the sorted list at the correct position
            sorted_list.insert(it, nums[i]);
        }
        
        // Since we traversed nums from right to left, reverse the result vector before returning
        reverse(result.begin(), result.end());
        
        return result;
    }
};

var countSmaller = function(nums) {
    // Result array to store the counts of smaller elements to the right
    const result = new Array(nums.length).fill(0);

    // To store the indices and values while we apply a modified merge sort
    const indices = nums.map((_, index) => index);

    // Helper function to perform merge sort and count smaller elements
    const mergeSort = (left, right) => {
        if (left >= right) {
            return;
        }

        // Find the mid-point
        const mid = Math.floor((left + right) / 2);

        // Recursively sort the left and right halves
        mergeSort(left, mid);
        mergeSort(mid + 1, right);

        // Create temporary arrays to store the current indices
        const temp = [];
        let i = left;        // Pointer for the left half
        let j = mid + 1;     // Pointer for the right half
        let rightCounter = 0; // Count of numbers moved from the right half

        // Merge the two halves while counting smaller elements
        while (i <= mid && j <= right) {
            if (nums[indices[i]] <= nums[indices[j]]) {
                // If left element is smaller or equal, move it to temp
                result[indices[i]] += rightCounter; // Add the rightCounter to the result
                temp.push(indices[i]);
                i++;
            } else {
                // If right element is smaller, move it to temp
                rightCounter++; // Increment rightCounter because this element is smaller
                temp.push(indices[j]);
                j++;
            }
        }

        // For remaining elements in the left half
        while (i <= mid) {
            result[indices[i]] += rightCounter;
            temp.push(indices[i]);
            i++;
        }

        // For remaining elements in the right half
        while (j <= right) {
            temp.push(indices[j]);
            j++;
        }

        // Copy back the sorted indices into the original array
        for (let k = left; k <= right; k++) {
            indices[k] = temp[k - left];
        }
    };

    // Start the merge sort process over the entire array
    mergeSort(0, nums.length - 1);

    // Return the result array containing counts of smaller elements to the right
    return result;
};

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        // Result list to store the counts of smaller elements to the right
        List<Integer> result = new ArrayList<>();

        // Base case: if the input array is empty, return an empty result list
        if (nums == null || nums.length == 0) {
            return result;
        }

        // Initialize the result list with 0s for each element in the input array
        for (int i = 0; i < nums.length; i++) {
            result.add(0);
        }

        // To store the indices and values while we apply a modified merge sort
        int[] indices = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            indices[i] = i;
        }

        // Helper function to perform merge sort and count smaller elements
        mergeSort(nums, indices, result, 0, nums.length - 1);

        return result;
    }

    // Helper function to perform merge sort and count smaller elements
    private void mergeSort(int[] nums, int[] indices, List<Integer> result, int left, int right) {
        // If the left index is greater or equal to right, no need to sort
        if (left >= right) {
            return;
        }

        // Find the mid-point
        int mid = (left + right) / 2;

        // Recursively sort the left and right halves
        mergeSort(nums, indices, result, left, mid);
        mergeSort(nums, indices, result, mid + 1, right);

        // Create a temporary array to store the current indices
        int[] temp = new int[right - left + 1];
        int i = left;        // Pointer for the left half
        int j = mid + 1;     // Pointer for the right half
        int k = 0;           // Pointer for the temp array
        int rightCounter = 0; // Count of numbers moved from the right half

        // Merge the two halves while counting smaller elements
        while (i <= mid && j <= right) {
            if (nums[indices[i]] <= nums[indices[j]]) {
                // If left element is smaller or equal, move it to temp
                result.set(indices[i], result.get(indices[i]) + rightCounter);
                temp[k++] = indices[i++];
            } else {
                // If right element is smaller, move it to temp
                rightCounter++;
                temp[k++] = indices[j++];
            }
        }

        // For remaining elements in the left half
        while (i <= mid) {
            result.set(indices[i], result.get(indices[i]) + rightCounter);
            temp[k++] = indices[i++];
        }

        // For remaining elements in the right half
        while (j <= right) {
            temp[k++] = indices[j++];
        }

        // Copy back the sorted indices into the original indices array
        for (int l = 0; l < temp.length; l++) {
            indices[left + l] = temp[l];
        }
    }
}