Leetcode Count of Smaller Numbers After Self problem solution

YASH PAL,

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;
}

coding problems