1. Runtime Distribution

2. Submission Details

3. Description

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].

4. Example

Given nums = [5, 2, 6, 1]
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.

6. Code

#include <limits.h>
#include <stdlib.h>
#include <stdio.h>

typedef struct segmentTree
{
    int min;
    int max;
    int count;
}segmentTree;

segmentTree* tree;

void buildTree(int l, int r, int current)
{
    tree[current].min = l;
    tree[current].max = r;
    tree[current].count = 0;
    if(l == r)
    {
        return;
    }
    int mid = tree[current].min + tree[current].max >> 1;
    buildTree(l, mid, current << 1);
    buildTree(mid + 1, r, current << 1 | 1);
}

int query(int num, int current)
{
    if(num >= tree[current].max)
    {
        return tree[current].count;
    }
    if(num < tree[current].min)
    {
        return 0;
    }

    if(num <=  tree[current].min + tree[current].max >> 1)
    {
        return query(num, current << 1);
    }

    return query(num, current << 1) + query(num, current << 1 | 1);
}

void insert(int num, int current)
{
    if(num < tree[current].min || num > tree[current].max)
    {
        return;
    }

    tree[current].count++;

    if(tree[current].min == tree[current].max)
    {
        return;
    }

    int mid = tree[current].min + tree[current].max >> 1;

    if(num <= mid)
    {
        insert(num, current << 1);
    }else
    {
        insert(num, current << 1 | 1);
    }
}

int* countSmaller(int* nums, int numsSize, int* returnSize) {

    int * result = (int *)malloc(sizeof(int*) * numsSize);
    *returnSize = numsSize;

    if(numsSize == 0)
    {
        return result;
    }

    int max = INT_MIN;
    int min = INT_MAX;

    for(int i = 0; i< numsSize; i++)
    {
        min = min > nums[i] ? nums[i] : min;
        max = max < nums[i] ? nums[i] : max;
    }

    tree = (segmentTree*)malloc(sizeof(segmentTree) * (max - min) * 4);

    buildTree(min, max, 1);

    for(int i = numsSize - 1; i >= 0; i--)
    {
        result[i] = query(nums[i] -1, 1);
        insert(nums[i], 1);
    }
    return result;
}

int main()
{
    int nums[] = { 1,9,7,8,5 };

    int *returnSize = malloc(sizeof(int));
    int * result= countSmaller(nums, 5, returnSize);
    for(int i = 0; i< *returnSize; i++)
    {
        printf("%d ", result[i]);
    }
    system("pause");
    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class LeetCode0315_2 {
    public List<Integer> countSmaller(int[] nums) {

        List<Integer> list = new ArrayList<Integer>();

        if (nums == null || nums.length == 0) {
            return list;
        }

        int len = nums.length;

        int[] idxs = new int[len];
        int[] count = new int[len];

        for (int i = 0; i < len; i++)
            idxs[i] = i;

        mergeSort(nums, idxs, 0, len, count);

        for (int i : count)
            list.add(i);

        return list;
    }

    private void mergeSort(int[] nums, int[] idxs, int start, int end, int[] count) {
        if (start + 1 >= end)
            return;

        int mid = (end - start) / 2 + start;
        mergeSort(nums, idxs, start, mid, count);
        mergeSort(nums, idxs, mid, end, count);

        merge(nums, idxs, start, end, count);
    }

    private void merge(int[] nums, int[] idxs, int start, int end, int[] count) {

        int mid = (end - start) / 2 + start;

        int[] tmpIdx = new int[end - start];
        int i = start, j = mid, k = 0;

        while (k < end - start) {
            if (i < mid) {
                if (j < end && nums[idxs[j]] < nums[idxs[i]]) {
                    tmpIdx[k++] = idxs[j++];
                } else {
                    count[idxs[i]] += j - mid;
                    tmpIdx[k++] = idxs[i++];
                }
            } else {
                tmpIdx[k++] = idxs[j++];
            }
        }

        System.arraycopy(tmpIdx, 0, idxs, start, end - start);
    }

    public static void main(String[] args) {
        int[] nums = { 5, 2, 6, 1 };
        LeetCode0315_2 leetcode = new LeetCode0315_2();
        List<Integer> result = leetcode.countSmaller(nums);
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i) + " ");
        }
    }
}

import java.util.LinkedList;
import java.util.List;

public class LeetCode0315_1 {

    private int[] tree;

    public List<Integer> countSmaller(int[] nums) {

        List<Integer> result = new LinkedList<Integer>();

        if (nums == null || nums.length == 0) {
            return result;
        }

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }

        tree = new int[max - min + 2];

        for (int i = nums.length - 1; i >= 0; i--) {
            int val = nums[i] - min + 1;
            result.add(0, sum(val - 1));
            update(val);
        }

        return result;
    }

    private int sum(int x) {
        int result = 0;
        while (x > 0) {
            result += tree[x];
            x -= lowBit(x);
        }

        return result;
    }

    private void update(int x) {
        while (x < tree.length) {
            tree[x]++;
            x += lowBit(x);
        }
    }

    private int lowBit(int x) {
        return x & (-x);
    }

    public static void main(String[] args) {
        int[] nums = { 5, 2, 6, 1 };
        LeetCode0315_1 leetcode = new LeetCode0315_1();
        System.out.println(leetcode.countSmaller(nums));
    }
}

import java.util.LinkedList;
import java.util.List;

public class LeetCode0315_4 {

    static class Tree {
        int left;
        int right;
        int count;

        Tree(int l, int r) {
            left = l;
            right = r;
        }
    }

    private Tree[] tree;
    private int min;
    private int max;

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new LinkedList<Integer>();
        if (nums == null || nums.length == 0) {
            return result;
        }

        int len = nums.length;

        min = Integer.MAX_VALUE;
        max = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }

        tree = new Tree[4 * (max - min + 1)];

        buildTree(min, max, 1);

        for (int i = len - 1; i >= 0; i--) {
            result.add(0, sum(nums[i] - 1, 1));
            update(nums[i], 1);
        }
        return result;
    }

    private void buildTree(int l, int r, int index) {
        if (l > r) {
            return;
        }
        tree[index] = new Tree(l, r);
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        buildTree(l, mid, index << 1);
        buildTree(mid + 1, r, index << 1 | 1);
    }

    private void update(int val, int index) {

        if (tree[index].left > val || tree[index].right < val) {
            return;
        }
        tree[index].count++;

        if (tree[index].left == tree[index].right) {
            return;
        }

        int mid = tree[index].left + ((tree[index].right - tree[index].left) >> 1);

        if (val <= mid) {
            update(val, index << 1);
        } else {
            update(val, index << 1 | 1);
        }
    }

    private int sum(int val, int index) {

        if (tree[index].right <= val) {
            return tree[index].count;
        }
        if (val < tree[index].left) {
            return 0;
        }

        int mid = tree[index].left + ((tree[index].right - tree[index].left) >> 1);

        if (val <= mid) {
            return sum(val, index << 1);
        } else {
            return sum(val, index << 1) + sum(val, index << 1 | 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = { 26, 78, 27, 100, 33, 67, 90, 23, 66, 5, 38, 7, 35, 23, 52, 22, 83, 51, 98, 69, 81, 32, 78, 28,
                94, 13, 2, 97, 3, 76, 99, 51, 9, 21, 84, 66, 65, 36, 100, 41 };
        LeetCode0315_4 leetcode = new LeetCode0315_4();
        System.out.println(leetcode.countSmaller(nums));
    }
}