Rank from Stream

Posted: 28 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an array of ‘N’ integers say ‘ARR’ and provided with other integer say ‘K’. Now you have to find the Rank of ‘ARR[K]’.

Note:

The rank of any element in ‘ARR’ is equal to the number of smaller elements than ‘ARR[K]’ on its left side.

For example :

Input :
Let ‘ARR’’ = [6, 2, 9, 7] and ‘X’ = 3.
We can see there are two smaller elements than ‘ARR[3]’ = 7 on its left side
Output: 2

Follow Up :

Try to find rank in less time complexity than O(N), you may use some data structure to implement this.

Input Format:

The first line of input contains a single integer T’, representing the number of test cases.
Then the ‘T’ test cases follow.

The first line of each test case contains two single space-separated numbers, ‘N’ and ‘K’, denoting the size of ‘ARR’, and the position of integer for which we have to find rank respectively.

The second line contains ‘N’ space-separated distinct integers denoting the array elements.

Output format:

For each test case, return a single integer representing the rank of ‘ARR[K]’.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints

1 <= T <= 100
1 <= N <= 10^4
1 <= K <= N
0 <=  ARR[i] <= 10^5

Time limit: 1 sec
Approach 1

The idea is to use the binary search tree.

 

First of all, we will make a binary search tree say ‘BST’ from the given array ‘ARR’ after this we can use ‘BST’ to find the rank of ‘ARR[K]’.

Each node of ‘BST’ will store the data value and size of its left subtree.

 

Here is the complete algorithm:

 

Step 1- Making the ‘BST’ :

 

Let insert(TreeNode* <int> ROOT, int VAL) be a function which insert data into ‘BST’.

Now consider the following steps to implement the function :

  1. If ‘ROOT’ is NULL then make a new Node with data and return it.
  2. If 'VAL' is less than data of ‘ROOT’ then do:
    1. Make a recursive call with the left child of ‘ROOT’ as ‘ROOT’.
    2. Increase the size of the left subtree of ‘ROOT’ by 1.
  3. Otherwise do:
    1. Make a recursive call with the right child of ‘ROOT’ as ‘ROOT’.

Now iterate over the ‘ARR’ and feed vales in ‘ARR’ to insert to generate ‘BST’.

 

Step2 -Find Rank of ‘ARR[K]’ say ‘NUM’ from ‘BST’:

 

Let getRank(TreeNode* <int> ROOT, int NUM) be a function that returns the size of the left subtree of the node with the value ‘NUM’ or we can say Rank of ‘NUM’. 

 

Now consider the following steps to implement the function :

  1. If data at ‘ROOT’ is equal to ‘NUM’ then return the size of the left subtree.
  2. If data at ‘ROOT’ is less than ‘NUM’ then do:
    1. Make a recursive call with the left child of ‘ROOT’ as ‘ROOT’.
  3. If data at ‘ROOT’ is greater than ‘NUM’ then do:
    1. Let RIGHT_SIZE = Make a recursive call with the right child of ‘ROOT’ as ‘ROOT’.
    2. Return (size of the left subtree+RIGHT_SIZE+1).
Try Problem