Do you think IIT Guwahati certified course can help you in your career?
Introduction
The rank of an element in-stream is the “Total number of elements which are equal to or less than x (not including x)”. A typical array search question is to find an element's rank in a stream. It is only easy when you know the right gest to the question. Otherwise, if you read the problem statement without knowing its meaning, you’ll find it a tricky question.
This article will discuss the problem of finding the rank of an element in a stream. We will use two approaches to find the solution to the given problem. The first is by linear traversal of the array. And then, by sorting and doing a binary search of the array.
Let’s see the problem statement of this question.
Problem Statement
We are given a key and a stream of elements. We need to find the rank of key value in that stream.
Sample Examples
Example 1:
Input:
arr[] = {15, 25, 20, 8, 9, 7, 1}, x = 9;
Output:
Rank of 9 in the stream is: 3
Explanation: Three elements are less than or equal to 9 (and not including 9).
Explanation: Eight elements are less than or equal to 25 (and not including 25).
Linear Traversal Approach
In this approach, find the rank of an element in a stream. We are comparing the key value element with all the array elements. Let’s see the algorithm of this approach.
Algorithm
We will start from the leftmost element of the array. And one by one, compare the key value x with each array element.
If x is greater than the element, increase the value of count by 1.
If x doesn’t match with any of the elements, return -1.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
//------------------Main Function------------------//
int main()
{
FAST;
int array[] = {8, 3, 17, 7, 18, 12, 10, 25, 13};
int key_value = 25;
int arraySize = sizeof(array)/sizeof(array[0]);
int count = 0;
for(int i = 0; i < arraySize; i++)
{
if(array[i] <= key_value)
{
count += 1;
}
}
cout << "Rank of the " << key_value << " in stream is: " << count-1 << endl;
return 0;
}
You can also try this code with Online C++ Compiler
The time complexity of the above-used approach is O(n), where n is the array's length. It is because we are comparing key values of all the components.
Space Complexity
The space complexity of the above-used approach is O(1), as no extra space is used.
Sorting and Binary Search Approach
A more straightforward way to implement this operation is to use an array. It will hold all the elements in sorted order. And when a new element is inserted, we would shift the elements. And then, we perform a binary search on the array to get the right-most element of x and return that element. The function to find rank would work in O(log n) time. But insertion operation would be costly.
Algorithm
We will use an array that will hold all the elements in sorted order.
Now when a new element is inserted, we would shift the elements.
Now, we traverse the tree from the root node and compare the root values to x. We will get the following cases.
When root->data == x, then return size of left subtree of root.
If x < root->data, then return getRank(root->left)
And if x > root->data, then return getRank(root->right) + size of left subtree + 1.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
class Node
{
public:
int data;
Node *left, *right;
int leftSize;
};
//----------------------Utility Function To Create New Node----------------------//
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
temp->leftSize = 0;
return temp;
}
//----------------------Utility Function To Insert Node----------------------//
Node* insertfxn(Node*& root, int data)
{
if (!root)
return newNode(data);
// Now updating the size of left subtree.
if (data <= root->data)
{
root->left = insertfxn(root->left, data);
root->leftSize++;
}
else
root->right = insertfxn(root->right, data);
return root;
}
//----------------------Utility Function To find rank of Node----------------------//
int findRank(Node* root, int x)
{
// When root->data == x, return size of left subtree of root.
if (root->data == x)
return root->leftSize;
//If x < root->data, return findRank(root->left)
if (x < root->data)
{
if (!root->left)
return -1;
else
return findRank(root->left, x);
}
//If x > root->data, return findRank(root->right) + size of left subtree + 1.
else
{
if (!root->right)
return -1;
else
{
int rightSize = findRank(root->right, x);
if(rightSize == -1 ) return -1;
return root->leftSize + 1 + rightSize;
}
}
}
//------------------Main Function------------------//
int main()
{
FAST;
int arr[] = {8, 3, 17, 7, 18, 12, 10, 25, 13};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 25;
Node* root = NULL;
for (int i = 0; i < n; i++)
root = insertfxn(root, arr[i]);
cout << "Rank of the " << x << " in stream is: "<< findRank(root, x) << endl;
return 0;
}
You can also try this code with Online C++ Compiler
The rank of a node in a tree is the number of nodes whose values are less than or equal to x. The nodes can be of any data type as long as they have an ordering relation.
How do you find the rank of an element?
The rank of an element in-stream is the “Total number of elements which are equal to or less than x (not including x)”. Here, if an element is not found in the stream or is the smallest in the stream, we will return -1.
What is meant by the rank of a matrix?
The rank of a matrix is the highest number of its linearly independent row vectors (or column vectors). From here, it is obvious that the rank of a matrix cannot surpass the number of its rows (or columns).
Conclusion
This article briefly discussed the problem of finding the rank of an element in a stream.
But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.
Nevertheless, you may consider our paid courses to give your career an edge over others!
84+ registered