# 315 Count of Smaller Numbers After Self

給一正整數矩陣，回傳一矩陣，存每個數字右邊有幾個比自己小的數字。 example:

Input: [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.

Idea 最簡單的作法就是依序拜訪每個element，也拜訪該element左邊所有element，若current element < 左邊element，左邊element的count+1，這樣就是O(n^2)

Code

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int[] res = new int[nums.length];
        for(int i=0; i<nums.length; i++){
            for(int j=0; j<i; j++){
                if(nums[i] < nums[j])
                    res[j]++;
            }
        }
        List<Integer> list = Arrays.stream(res).boxed().collect(Collectors.toList()); 
        return list;
    }
}

最後TLE無法AC，所以再進一步優化。

Idea 用另一個list存拜訪過的元素，並將之排序。 每次拜訪一新element，去那個list用binary search搜尋，這樣就可以把時間複雜度降到O(nlogn)

Pseudocode

sorted - list of element that has been visited, ascending order
traverse from right to left
    res[i] = the index which is the first number larger then current number
    add current number to sorted, and sort again
return res

code

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> sorted = new ArrayList<>();
        Integer[] res = new Integer[nums.length];
        for(int i=nums.length-1; i>=0; i--){
            res[i] = findIndex(sorted, nums[i]);
            sorted.add(res[i],nums[i]);
        }
        return Arrays.asList(res);
    }

    private int findIndex(List<Integer> sorted, int target){
        if(sorted.size()==0)  return 0;
        int start = 0, end = sorted.size()-1;

        if(sorted.get(end) < target)    return end+1;
        if(sorted.get(0) > target)    return start;

        while(start+1 < end){
            int mid = start + (end-start)/2;
            if (sorted.get(mid) < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        if (sorted.get(start) >= target) return start;
        return end;
    }

}

這個解法可以AC，但performance還不夠好。

Idea 用binary index tree。BIT的use case通常是要求element 0~n 的總和。以這題來說，BIT的每個node代表某數字，我們可以在BIT中存某數字的次數(freq)。若我們從右拜訪到左，先放入BIT的比當下數字小的freq總和就是我們想放入當下node的數字。 有這個idea之後，之後的操作就照BIT標準get, update操作就可以了。

Pseudocode

Integer[] res to save countSmaller of each num
    get min and max of nums
    create a tree which is size of max
    go through nums from right to left
        res[i] = get(nums[i]-1, tree)
        update(nums[i], tree)

    update(idx, tree):
        while idx < tree.length
            ++tree[idx];
            idx+= idx & -idx;

    get(idx, tree):
        while idx > tree.length
            res+= tree[idx]
            idx -= idx & -idx

Code

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        if (nums.length == 0) return new ArrayList<>();
        Integer[] res = new Integer[nums.length];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; ++i) {
            min = Math.min(min, nums[i]);
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; ++i) {
            nums[i] =  nums[i] - min + 1;
            max = Math.max(max, nums[i]);
        }

        int[] tree = new int[max + 1];
        for (int i = nums.length - 1; i >= 0; --i) {
            res[i] = get(nums[i] - 1, tree);
            update(nums[i], tree);
        }
        return Arrays.asList(res);
    }

    private void update(int idx, int[] tree) {
        while (idx < tree.length) {
            ++tree[idx];
            idx += idx & -idx;
        }
    }

    private int get(int idx, int[] tree) {
        int res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & -idx;
        }
        return res;
    }
}