Posts Right Smaller Than
Post
Cancel

Right Smaller Than

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

snapshot

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;
  }
}
This post is licensed under CC BY 4.0 by the author.