315. Count of Smaller Numbers After Self

// Solution 0: Binary Indexed Tree
class Solution {
    int[] a;
    int[] count;
    public List<Integer> countSmaller(int[] nums) {
        map(nums);
        count = new int[a.length];
        
        List<Integer> res = new ArrayList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            int id = Arrays.binarySearch(a, nums[i]) + 1;
            res.add(query(id - 1));
            update(id);
        }
        
        Collections.reverse(res);
        return res;
    }
    
    private int lowBit(int i) {
        return i & (-i);
    }
    
    private int query(int i) {
        int res = 0;
        while (i > 0) {
            res += count[i];
            i -= lowBit(i);
        }
        return res;
    }
    
    private void update(int i) {
        while (i < count.length) {
            count[i] += 1;
            i += lowBit(i);
        }
    }
    
    private void map(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        a = new int[numSet.size()];
        int index = 0;
        for (int num : numSet) {
            a[index++] = num;
        }
        Arrays.sort(a);
    }
}
// Solution 1: Divide and Conquer
class Solution {
    class Item {
        int val;
        int index;
        public Item(int v, int i) {
            val = v;
            index = i;
        }
    }

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(nums[i], i);
        }

        int[] count = new int[n];
        mergeSort(items, 0, n - 1, count);
        List<Integer> res = new ArrayList<>();
        for (int i : count) {
            res.add(i);
        }
        return res;
    }

    private void mergeSort(Item[] items, int lo, int hi, int[] count) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(items, lo, mid, count);
        mergeSort(items, mid + 1, hi, count);
        merge(items, lo, mid, mid + 1, hi, count);
    }

    private void merge(Item[] items, int lo, int loEnd, int hi, int hiEnd, int[] count) {
        int m = hiEnd - lo + 1;
        Item[] sorted = new Item[m];
        int rightCounter = 0;
        int loPtr = lo, hiPtr = hi;
        int index = 0;
        while (loPtr <= loEnd && hiPtr <= hiEnd) {
            if (items[loPtr].val > items[hiPtr].val) {
                rightCounter++;
                sorted[index++] = items[hiPtr++];
            } else {
                count[items[loPtr].index] += rightCounter;
                sorted[index++] = items[loPtr++];
            }
        }

        while (loPtr <= loEnd) {
            count[items[loPtr].index] += rightCounter;
            sorted[index++] = items[loPtr++];
        }

        while (hiPtr <= hiEnd) {
            sorted[index++] = items[hiPtr++];
        }

        System.arraycopy(sorted, 0, items, lo, m);
    }
}