PROBLEM DESCRIPTION
Write a function that takes in an array of integers and returns an array of the same length where each element in the output array corresponds to the number of integers in the input array that are to the right of the relevant index and that are strictly smaller than the integer at that index.
SOLUTION
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
import java.util.*;
class Program {
static List<Integer> ans = new ArrayList<>();
static class BSTNode{
int val;
int LST;
BSTNode left;
BSTNode right;
BSTNode(int val){
this.val = val;
LST = 0;
left = null;
right = null;
}
BSTNode insert(BSTNode root, int k, int[] count){
if(root == null){
root = new BSTNode(k);
return root;
}
if(k < root.val){
root.LST++;
root.left = insert(root.left, k, count);
}else{
if(k > root.val){
count[0]++;
}
count[0] += root.LST;
root.right = insert(root.right, k, count);
}
return root;
}
}
public static List<Integer> rightSmallerThan(List<Integer> array) {
if(array.size() == 0) return new ArrayList<>();
if(array.size() == 1) return Arrays.asList(new Integer[]{0});
ans = new ArrayList<>();
BSTNode root = new BSTNode(array.get(array.size()-1));
ans.add(0);
for(int i=array.size()-2; i>=0; i--){
int k = array.get(i);
int[] c = new int[1];
root.insert(root, k, c);
ans.add(c[0]);
}
Collections.reverse(ans);
return ans;
}
}