315. Count of Smaller Numbers After Self

https://leetcode.com/problems/count-of-smaller-numbers-after-self/?tab=Description

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

1
2
3
4
5
6
7
8
9
Example:

Given nums = [5, 2, 6, 1]

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.
Return the array [2, 1, 1, 0].

cpp


https://discuss.leetcode.com/topic/31288/c-o-nlogn-time-o-n-space-mergesort-solution-with-detail-explanation

C++ O(nlogn)-Time O(n)-Space MergeSort Solution with Detail Explanation

MergeSort-based solution is a standard way to solve problems related to inverse numbers.

Here is an example to illustrate the general idea of MergeSort-based algorithm:

Now we want to consider an array

1
6 4 1 8 7 5 2 9

First thing first, split the array into to subarrays:

1
2
6 4 1 8
7 5 2 9

and then calculate the inverse numbers within the group:

1
2
1 4(1) 6(1,4) 8
2 5(2) 7(2,5) 9

where the numbers in the parentheses are the numbers that should be counted when we calculate the inverse number.
Now we need to merge these two arrays into one sorted array. The first element to be put into the sorted destination array is the “1” in the first array.

1
2
1               4(1) 6(1,4) 8
2 5(2) 7(2,5) 9 merged elements in the 2nd array = ()

The second element to merge is the “2” in the second array:

1
2
1 2                4(1) 6(1,4) 8
5(2) 7(2,5) 9 merged elements in the 2nd array = (2)

The third element to merge is the “4” in the first array:

1
2
1 2 4(1,2)              6(1,4) 8
5(2) 7(2,5) 9 merged elements in the 2nd array = (2)

When we merge the “4(1)”, we found that “4” is actually greater than all merged elements in the second array (i.e. [2]). Therefore, we also need to consider those elements. Therefore, the numbers in the parenthese of 2 become (1)+(2) = (1,2). Next step:

1
2
1 2 4(1,2) 5(2)         6(1,4) 8
7(2,5) 9 merged elements in the 2nd array = (2,5)

Next (add the inverse number of element “6” by 2)

1
2
1 2 4(1,2) 5(2) 6(1,4,2,5)     8
7(2,5) 9 merged elements in the 2nd array = (2,5)

So and so forth, finally reach

1
2
1 2 4(1,2) 5(2) 6(1,4,2,5) 7(2,5) 8(2,5,7) 9
merged elements in the 2nd array = (2,5,7,9)

Additionally, when we need to count the inverse number, we do not need to record the exact elements, we only need to record the numbers. So, we can use a variable to record the number of “merged elements in the 2nd array” (for example, semilen in the code beneath) and the number of smaller elements of each element (for example, results[idx] in the code beneath).

Complexities:

Time: O(n log n)

Space: O(n)

C++ Accepted Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
protected:
void merge_countSmaller(vector<int>& indices, int first, int last,
vector<int>& results, vector<int>& nums) {
int count = last - first;
if (count > 1) {
int step = count / 2;
int mid = first + step;
merge_countSmaller(indices, first, mid, results, nums);
merge_countSmaller(indices, mid, last, results, nums);
vector<int> tmp;
tmp.reserve(count);
int idx1 = first;
int idx2 = mid;
int semicount = 0;
while ((idx1 < mid) || (idx2 < last)) {
if ((idx2 == last) || ((idx1 < mid) &&
(nums[indices[idx1]] <= nums[indices[idx2]]))) {
tmp.push_back(indices[idx1]);
results[indices[idx1]] += semicount;
++idx1;
} else {
tmp.push_back(indices[idx2]);
++semicount;
++idx2;
}
}
move(tmp.begin(), tmp.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_countSmaller(indices, 0, n, results, nums);
return results;
}
};

https://discuss.leetcode.com/topic/31291/c-short-solution-using-binary-indexed-tree-56-ms

C++ short solution using binary indexed tree (56 ms)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> ret, clone = nums;;
int len = (int) nums.size();
unordered_map<int, int> reflect;
array.resize(len + 1);
sort(clone.begin(), clone.end());
for (int i = 0; i < len; ++ i)
reflect[clone[i]] = i + 1;

for (int i = len - 1; i >= 0; -- i) {
clone[i] = query(reflect[nums[i]] - 1);
add(reflect[nums[i]], 1);
}
return clone;
}

private:
vector<int> array;
inline int lowbit(int pos) {
return pos & -pos;
}
void add(int pos, int val) {
long len = array.size();
while (pos < len) {
array[pos] += val;
pos += lowbit(pos);
}
}
int query(int pos) {
int ret = 0;
while (pos > 0) {
ret += array[pos];
pos -= lowbit(pos);
}
return ret;
}
};

https://discuss.leetcode.com/topic/36736/c-14-line-solution

C++ 14 line solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> db;
vector<int> result(nums.size());
for(int i = nums.size()-1; i >= 0; i--)
{
auto it = lower_bound(db.begin(), db.end(), nums[i]);
result[i] = it - db.begin();
db.insert(it, nums[i]);
}
return result;
}
};

python


https://discuss.leetcode.com/topic/31162/mergesort-solution

Mergesort solution

The smaller numbers on the right of a number are exactly those that jump from its right to its left during a stable sort. So I do mergesort with added tracking of those right-to-left jumps.

Update, new version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def countSmaller(self, nums):
def sort(enum):
half = len(enum) / 2
if half:
left, right = sort(enum[:half]), sort(enum[half:])
for i in range(len(enum))[::-1]:
if not right or left and left[-1][1] > right[-1][1]:
smaller[left[-1][0]] += len(right)
enum[i] = left.pop()
else:
enum[i] = right.pop()
return enum
smaller = [0] * len(nums)
sort(list(enumerate(nums)))
return smaller

Old version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def countSmaller(self, nums):
def sort(enum):
half = len(enum) / 2
if half:
left, right = sort(enum[:half]), sort(enum[half:])
m, n = len(left), len(right)
i = j = 0
while i < m or j < n:
if j == n or i < m and left[i][1] <= right[j][1]:
enum[i+j] = left[i]
smaller[left[i][0]] += j
i += 1
else:
enum[i+j] = right[j]
j += 1
return enum
smaller = [0] * len(nums)
sort(list(enumerate(nums)))
return smaller

https://discuss.leetcode.com/topic/33908/3-ways-segment-tree-binary-indexed-tree-binary-search-tree-clean-python-code

3 ways (Segment Tree, Binary Indexed Tree, Binary Search Tree) clean python code

Segment Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
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=None):
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=None):
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):
hashTable = {v: i for i, v in enumerate(sorted(set(nums)))}

tree, r = SegmentTree(len(hashTable)), []
for i in xrange(len(nums) - 1, -1, -1):
r.append(tree.sum(0, hashTable[nums[i]] - 1))
tree.update(hashTable[nums[i]], 1)
return r[::-1]
Binary Indexed Tree

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]

Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class BinarySearchTreeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.count = 1
self.leftTreeSize = 0


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

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

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

if val < root.val:
root.leftTreeSize += 1

if not root.left:
root.left = BinarySearchTreeNode(val)
return 0
return self.insert(val, root.left)

if not root.right:
root.right = BinarySearchTreeNode(val)
return root.count + root.leftTreeSize

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


class Solution(object):
def countSmaller(self, nums):
tree = BinarySearchTree()
return [
tree.insert(nums[i], tree.root)
for i in xrange(len(nums) - 1, -1, -1)
][::-1]

java


10ms, 80.82%, October 18, 2016

https://discuss.leetcode.com/topic/31405/9ms-short-java-bst-solution-get-answer-when-building-bst

9ms short Java BST solution get answer when building BST

Every node will maintain a val sum recording the total of number on it’s left bottom side, dup counts the duplication. For example, [3, 2, 2, 6, 1], from back to beginning,we would have:

1
2
3
4
5
6
7
1(0, 1)
\
6(3, 1)
/
2(0, 2)
\
3(0, 1)

When we try to insert a number, the total number of smaller number would be adding dup and sum of the nodes where we turn right.
for example, if we insert 5, it should be inserted on the way down to the right of 3, the nodes where we turn right is 1(0,1), 2,(0,2), 3(0,1), so the answer should be (0 + 1)+(0 + 2)+ (0 + 1) = 4

if we insert 7, the right-turning nodes are 1(0,1), 6(3,1), so answer should be (0 + 1) + (3 + 1) = 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
}
}
谢谢你,可爱的朋友。