Rank from Stream

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
Morgan StanleyMicrosoftOla

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample input 1:

2
4 1
4 8 2 10
6 2
6 8 5 1 9 9

Sample output 1:

1
0

Explanation for sample input 1:

For test case 1:
There is only one smaller element than 8 on its left side.
For test case 2:
There is only no smaller element than 5 on its left side.

Sample input 2:

2
5 3
1 4 3 4 5
6 5
6 4 3 2 1 7

Sample output 2:

2
5

Explanation for sample input 2:

For test case 1:
There there are 2 smaller elements than 8 on its left side.
For test case 2:
All the elements on the left side of 7 are smaller, return 5.
Hint

Try to think of a Data structure that inserts and sorts the data in logN time.

Approaches (1)
Binary Search Tree

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).
Time Complexity

O(N), where ‘N’ is the size of the array ‘ARR’.

 

In the worst-case scenario, if the binary search tree is left-skewed or right-skewed then the algorithm will make ‘N’ computations.

Space Complexity

O(N), where ‘N’ is the size of the array ‘ARR’.

 

Since we are doing a recursive tree traversal and in the worst case (Skewed Trees), all nodes of the given tree can be stored in the call stack. So the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Rank from Stream
Full screen
Console