Similarity

• Break down the array and solve for the subproblems

Three Implementation

• Merge sort(guarantee O(nlogn))
• BST(worst case O(n^2). Consider balanced-tree for insertion)
• BIT(O(nlogn))

315 Count of Smaller Numbers After Self

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

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.

BST Solution

• Node属性有：val表示Node的值，sum表示它左子树上总共的number，dup表示这个Node相同值的总共个数。
• 根据给的数组从后往前建树，对每个插入的数，将插入的path上所有turn right的Node的sum和dup相加得到新Node的smaller numbers after self的个数，即把新插入的点后面的所有比它小的Node中，比Node小的数的个数和Node自身的dup个数相加。

public class Solution {
    class Node {
        Node left, right;
        int val, sum, dup = 1;
        public Node(int v, int s) {
            val = v;
            sum = s;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        Integer[] ans = new Integer[nums.length];
        Node root = null;
        for (int i = nums.length - 1; i >= 0; i--) {
            root = insert(nums[i], root, ans, i, 0);
        }
        return Arrays.asList(ans);
    }
    private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {
        if (node == null) {
            node = new Node(num, 0);
            ans[i] = preSum;
        } else if (node.val == num) {
            node.dup++;
            ans[i] = preSum + node.sum;
        } else if (node.val > num) {
            node.sum++;
            node.left = insert(num, node.left, ans, i, preSum);
        } else {
            node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);
        }
        return node;
    }
}

MergeSort Solution

• MergeSort-based solution is a standard way to solve problems related to inverse numbers.
• 把一个array对半分为left array和right array，有一个rightcount，当merge时加入一个右子数组的数，说明左子数组中的每个数都有一个比它小的数在右边，所以rightcount加一；当merge时加入一个左子数组的数，就加上当前的rightcount

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int[] count = new int[nums.length];
        int[] indexes = new int[nums.length];
        for (int i=0; i<indexes.length; i++) {
            indexes[i] = i;
        }
        mergeSort(nums, count, indexes, 0, nums.length - 1);
        List<Integer> res = new ArrayList<Integer>();
        for (int i=0; i<nums.length; i++) {
            res.add(count[i]);
        }
        return res;
    }
    public void mergeSort(int[] nums, int[] count, int[] indexes, int start, int end) {
        if (end <= start) return;
        int mid = (start + end) / 2;
        mergeSort(nums, count, indexes, start, mid);
        mergeSort(nums, count, indexes, mid + 1, end);
        merge(nums, count, indexes, start, end);
    }
    public void merge(int[] nums, int[] count, int[] indexes, int start, int end) {
        int mid = (start + end) / 2;
        int left_index = start;
        int right_index = mid+1;
        int rightcount = 0;     
        int[] new_indexes = new int[end - start + 1];

        int sort_index = 0;
        while(left_index <= mid && right_index <= end){
            if(nums[indexes[right_index]] < nums[indexes[left_index]]){
                new_indexes[sort_index] = indexes[right_index];
                rightcount++;
                right_index++;
            }else{
                new_indexes[sort_index] = indexes[left_index];
                count[indexes[left_index]] += rightcount;
                left_index++;
            }
            sort_index++;
        }
        while(left_index <= mid){
            new_indexes[sort_index] = indexes[left_index];
            count[indexes[left_index]] += rightcount;
            left_index++;
            sort_index++;
        }
        while(right_index <= end){
            new_indexes[sort_index++] = indexes[right_index++];
        }
        for(int i = start; i <= end; i++){
            indexes[i] = new_indexes[i - start];
        }
    }
}

BIT Solution

• Both update() and query() operation have O(n) time complexity.
• Space complexity: O(n)
• Tree length is determined by maximum value of nums. Use long instead of integer in case it overflows
• Pre-process the input array to guarantee no negative element leading to an out of index exception

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) return res;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
        }
        int[] nums2 = new int[nums.length];
        for (int i=0; i<nums.length; i++) {
            nums2[i] = nums[i] - min + 1;
            max = Math.max(max, nums2[i]);
        }
        int[] tree = new int[max + 1];
        for (int i=nums2.length-1; i>=0; i--) {
            res.add(0, query(nums2[i] - 1, tree));
            update(nums2[i], tree);
        }
        return res;
    }
    private int query(int i, int[] tree) {
        int num = 0;
        while (i > 0) {
            num += tree[i];
            i -= i & (-i);
        }
        return num;
    }
    private void update(int i, int[] tree) {
        while (i < tree.length) {
            tree[i] ++;
            i += i & (-i);
        }
    }
}

493 Reverse Pairs

BST Solution

• 建树时，如果插入的新的值等于一个节点的值，增加dup；如果小于这个节点的值，把这个节点的less增加一并对它的左子节点插入这个值
• search时，要找小于target(target = (double) nums[i] / 2)的值，当找到节点的值等于target，直接加上less即小于该节点的节点个数；当找到的节点的值大于target，往左子树找；当找到的节点的值小于target，加上该节点的less并往右子树中找满足要求的节点
• 对sorted array(worst case)会超时

class Solution {
    public int reversePairs(int[] nums) {
        Node root = null;
        int cnt = 0;
        for (int i=nums.length-1; i>=0; i--) {
            cnt = search(cnt, root, nums[i] / 2.0);
            root = buildTree(nums[i], root);
        }
        return cnt;
    }
    private Node buildTree(int val, Node node) {
        if (node == null) return new Node(val);
        if (node.val == val) {
            node.dup ++;
        }
        else if (node.val > val) {
            node.less ++;
            node.left = buildTree(val, node.left);
        }
        else {
            node.right = buildTree(val, node.right);
        }
        return node;
    }
    private int search(int cnt, Node node, double target) {
        if (node == null) return cnt;
        if (target < node.val) {
            return search(cnt, node.left, target);
        }
        else if (target == node.val) {
            return cnt + node.less;
        }
        else {
            return search(cnt + node.less + node.dup, node.right, target);
        }
    }
}
class Node {
    int val, less, dup;
    Node left, right;
    public Node(int _val) {
        val = _val;
        dup = 1;
    }
}

MergeSort Solution

• 对每个右数组的数，如果它和左数组的nums[i]能够满足条件，那么它就能和左数组中第i+n(n>=0)元素满足条件。
• 用/2.0防止overflow

class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }
    private int mergeSort(int[] nums, int start, int end) {
        if (start >= end) return 0;
        int mid = start + (end - start) / 2;
        int cnt = mergeSort(nums, start, mid) + mergeSort(nums, mid+1, end);
        for (int i=start, j=mid+1; i<=mid; i++) {
            while (j <= end && nums[i] / 2.0 > nums[j]) j ++;
            cnt += j - (mid + 1);
        }
        Arrays.sort(nums, start, end + 1);
        return cnt;
    }
}

BIT Solution

• 把int array转换成long array防止overflow
• 两个operation：从左到右search(2 * num + 1）在sorted array中的位置，并query()比它大的数；update() index with the accumulated count
• Arrays.binarySearch : If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        
        // why long? 2 * nums[i] could overflow
        // why this array? need its indexes to build bit
        long[] nums2 = new long[n];
        for (int i = 0; i < n; i++) {
            nums2[i] = (long)nums[i];
        }
        Arrays.sort(nums2);
        
        int[] bit = new int[n + 1];
        
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int curr = nums[i];
            
            int idx1 = Arrays.binarySearch(nums2, 2l * curr + 1);
            count += query(bit, (idx1 < 0 ? -(idx1 + 1) : idx1) + 1);

            int idx2 = Arrays.binarySearch(nums2, curr);
            insert(bit, (idx2 < 0 ? -(idx2 + 1) : idx2) + 1, 1);
        }
        
        return count;    
    }
    
    private int query(int[] bit, int x) {
        int res = 0;
        
        for (int i = x; i < bit.length; i += i & -i) {
            res += bit[i];
        }
        
        return res;
    }
    
    private void insert(int[] bit, int x, int val) {
        for (int i = x; i > 0; i -= i & -i) {
            bit[i] += val;
        }
    }
}

Reference

General principles behind problems similar to "Reverse Pairs"