## 315. Count of Smaller Numbers After Self

You are given an integer arraynumsand you have to return a newcountsarray. Thecountsarray 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.
``````

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){
}
// if (ans.isEmpty()){
//     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;
}
};
``````