315. Count of Smaller Numbers After Self

You are given an integer arraynumsand you have to return a newcountsarray. Thecountsarray has the property wherecounts[i]is the number of smaller elements to the right ofnums[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.

Thoughts:

1. Failed to use template for positive entry... (attaching the code)

2. d

Code that I failed to implement (failed to handle properly the negative case):

class Solution {
    class SegmentTreeNode{
    public int start , end, cnt;
    public SegmentTreeNode left, right;
    public SegmentTreeNode (int start, int end, int cnt){
        this.start = start;
        this.end = end;
        this.cnt = cnt;
        this.left = this.right = null;
    }

    }
    public List<Integer> countSmaller(int[] nums) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int num: nums){
            if (num > max)
                max = num;
            if (num < min)
                min = num;
        }
        // System.out.println("1: max: " + max);
        SegmentTreeNode root = build(min, max);
        List<Integer> ans = new ArrayList<Integer>();
        int [] record = new int[nums.length]; 
        for (int i = nums.length - 1; i >=0; i--){
            // if(nums[i] > 0){

                record[i] = query(root, min, nums[i] - 1);
                System.out.println("i: " + i + "; nums[i]: " + nums[i] + " query: " + query(root, min, nums[i] - 1));

                modify(root, nums[i], 1);
            // }
        }
        for(int num: record){
            ans.add(num);
        }
        // if (ans.isEmpty()){
        //     ans.add(0);
        //     return ans;
        // }
        return ans;
    }
    public SegmentTreeNode build (int start, int end){
        if (start > end){
            return null;
        }
        if(start == end){
            return new SegmentTreeNode (start, end, 0);
        }

        int mid = (start + end) / 2;
        if(mid == end){
            mid -= 1;
        }
        System.out.println("build start: " + start + " end: " + end + " mid: " + mid);
        SegmentTreeNode left = build(start, mid);
        SegmentTreeNode right = build(mid + 1, end);
        SegmentTreeNode ret = new SegmentTreeNode (start, end, 0);
        ret.left = left;
        ret.right = right;

        return ret; 
    }
    public void modify(SegmentTreeNode root, int index, int val){
        if(root.start == root.end && root.end == index ){
            root.cnt = val;
            // System.out.println("index: " + index + " modified as: " + val);
            return;
        }
        int mid = (root.start + root.end) /2 ;
         if(mid == root.end){
            mid -= 1;
        }
        if(root.start <= index && index <=mid){
            modify(root.left, index, val);
        }
        if(mid < index && index <= root.end) {
            modify(root.right, index, val);
        }

        root.cnt = root.left.cnt + root.right.cnt;
        return;
    }

    public int query(SegmentTreeNode root, int start, int end){
        if(start > end) return 0;
        int mid = (root.start + root.end) / 2;
         if(mid == root.end){
            mid -= 1;
        }
        System.out.println("Query start: " + start + " end: " + end + 
                           "; root start: " + root.start + " root end: " + root.end + " mid: "  + mid
                          );
        if (start == root.start && root.end == end){
            System.out.println("exact!");
            return root.cnt;
        }

        int ret = 0;
        if (start <= mid ){
             System.out.println("left!");
            ret += query(root.left, start, mid);
        }
        if (mid + 1 <= end ){
            System.out.println("right!");
            ret += query(root.right, mid + 1, end);

        }

        return ret;
    }
}

SegmentTree implementation:

class SegmentTreeNode(object):
    def __init__ (self, val , start, end):
        self.val = val
        self.start = start 
        self.end = end
        self.children = []

class SegmentTree(object):
    def __init__ (self, n):
        self.root = self.build(0, n - 1)

    def build(self, start, end):
        if start > end:
            return

        root = SegmentTreeNode(0, start, end)

        if start == end:
            return root
        mid = start + end >> 1
        root.children = filter(None, [
            self.build(start, end)
            for start, end in ((start, mid),(mid + 1, end))
        ]) 

        return root

    def update(self, i, val, root):
        # root = root or self.root
        if i < root.start or i > root.end:
            return root.val
        if i == root.start == root.end:
            root.val += val 
            return root.val 

        root.val = sum([self.update(i, val, c) for c in root.children])
        return root.val

    def sum(self, start, end, root):
        # root = root or self.root
        if end < root.start or start > root.end:
            return 0

        if start <= root.start and end >= root.end:
            return root.val

        return sum([self.sum(start, end, c) for c in root.children])

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        table = {v : i for i , v in enumerate(sorted(set(nums)))}
        # print(table)
        tree , r  = SegmentTree(len(table)), []
        for i in range(len(nums) - 1, -1, -1):
            r.append(tree.sum(0, table[nums[i]] - 1, tree.root))
            tree.update(table[nums[i]], 1, tree.root)

        return r[::-1]

BinaryIndexedTree implementation:

class BinaryIndexedTree(object):
    def __init__(self, n):
        self.sums = [0] * (n + 1)

    def update(self, i, val):
        while i < len(self.sums):
            self.sums[i] += 1
            i += i & -i

    def sum(self, i):
        r = 0
        while i > 0:
            r += self.sums[i]
            i -= i & -i
        return r


class Solution(object):
    def countSmaller(self, nums):
        hashTable = {v: i for i, v in enumerate(sorted(set(nums)))}

        tree, r = BinaryIndexedTree(len(hashTable)), []
        for i in xrange(len(nums) - 1, -1, -1):
            r.append(tree.sum(hashTable[nums[i]]))
            tree.update(hashTable[nums[i]] + 1, 1)
        return r[::-1]

BinarySearchTree implementation:

class BSTNode(object):
    def __init__ (self, val):
        self.val = val 
        self.left = None
        self.right = None
        self.count = 1
        self.leftTreeSum = 0

class BST(object):
    def __init__ (self):
        self.root = None

    def insert(self, val, root):
        if not root:
            self.root = BSTNode(val);
            return 0

        if val == root.val:
            root.count += 1
            return root.leftTreeSum

        if val < root.val:
            root.leftTreeSum += 1
            if not root.left:
                root.left = BSTNode(val)
                return 0
            return self.insert(val, root.left)

        if not root.right:
            root.right = BSTNode (val)
            return root.count + root.leftTreeSum 

        return root.count + root.leftTreeSum + self.insert(val, root.right)


class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        tree = BST()
        return [tree.insert(
            nums[i], tree.root)
            for i in range(len(nums) -1, -1 , -1)
            ][::-1]

MergeSort implementation T: O(nlogn) S: O(n)

class Solution {

protected:
    void merge(vector<int>& indices, int first, int last, 
               vector<int>& results, vector<int>&nums){
        int mid = first + (last - first)/2;
        if(mid > first){
            merge(indices, first, mid, results, nums);
            merge(indices, mid, last, results, nums);
            vector<int> sorted;
            int subchild = 0;
            int idx1 = first, idx2 = mid;
            while((idx1 < mid) || (idx2 < last)){ 
                if((idx2 == last) || ((idx1 < mid)  &&
                                     (nums[indices[idx1]] <= nums[indices[idx2]]) // must be <= since only counts numbers that are SMALLER
                                     )) {  //3
                    sorted.push_back(indices[idx1]);
                    results[indices[idx1]] += subchild;
                    idx1++;
                }
                else{
                    sorted.push_back(indices[idx2]);
                    subchild++;
                    idx2++;
                }
            }

            move(sorted.begin(), sorted.end(), indices.begin() + first);
        }
    }

public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> results (n, 0);
        vector<int> indices (n, 0);
        iota (indices.begin(), indices.end(), 0);
        merge(indices, 0, n, results, nums);
        return results;
    }
};