In this Leetcode Count of Smaller Numbers After Self problem solution 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].

Leetcode Count of Smaller Numbers After Self problem solution


Problem solution in Python.

class Solution:
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        tmp = []
        ans = []
        for i in nums[::-1]:
            x = bisect.bisect_left(tmp, i)
            ans.append(x)
            tmp.insert(x, i)
        
        return ans[::-1]



Problem solution in Java.

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        ArrayList<Integer>a = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            int count = 0;
            for(int j = i + 1; j < nums.length; j++){
                if(nums[i]> nums[j]){
                    count++;
                }
            }
            a.add(count);
        }
        return a;
        
    }
}


Problem solution in C++.

vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size(), 0), sorted;
        for (int i = nums.size() - 1; i >= 0; i--) {
            auto loc = lower_bound(sorted.begin(), sorted.end(), nums[i]);
            res[i] = loc - sorted.begin();
            sorted.insert(loc, nums[i]);
        }
        return res;
    }


Problem solution in C.

struct SearchTree
{
    int val;
    int count;
    struct SearchTree* left;
    struct SearchTree* right;
};

struct SearchTree* Insert(struct SearchTree* T, int x, int* count_small)
{
    if(T == NULL)
    {
        T = (struct SearchTree*)malloc(sizeof(struct SearchTree));
        T->val = x;
        T->count = 0;
        T->left = NULL;
        T->right = NULL;
    }
    else
    {
        if(x <= T->val)
        {
            T->count++;
            T->left = Insert(T->left, x, count_small);
        }
        else
        {
            *count_small = *count_small + T->count + 1;
            T->right = Insert(T->right, x, count_small);
        }
    }
    
    return T;
}

int* countSmaller(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;
    int *result = (int*)malloc(sizeof(int) * numsSize);
    struct SearchTree* T = NULL;
    
    for(int i = numsSize - 1; i >= 0; --i)
    {
        int count_small = 0;
        T = Insert(T, nums[i], &count_small);
        result[i] = count_small;
    }
    
    return result;
}