In this guide, we will explore the process of calculating the number of smaller elements on the right-hand side in C++ through multiple illustrations.
Below is an unsorted array arr with unique integers in N dimensions. The goal is to generate a secondary array named count with a reduced count. This array will display the number of elements to the right of the array that are smaller than arr[i], represented by the smaller[i] variable.
Sample examples:
Example:1
Input:
N = 5, arr = {7, 4, 6, 2, 1}
Output:
{3, 2, 2, 1, 0}
Explanation:
- For arr[0] , there are three elements on the right side that are smaller than 7, which are {4, 6, 2}.
- For arr[1] , there are two elements on the right side that are smaller than 4, which are {2, 1}.
- For arr[2] , there are two elements on the right side that are smaller than 6, which are {2, 1}.
- For arr[3] , there is one element on the right side that is smaller than 2, which is {1}.
- For arr[4] , there are no elements on the right side that are smaller.
Example 2:
Input:
N=5, arr = {7, 1, 5, 2, 10}
Output:
{3, 0, 0, 2, 0}
Explanation:
- Three of the items on the right side are smaller for arr[0] .
- 0 items on the right side are smaller for arr[1] .
- 0 items on the right side are smaller for arr[2] .
- Two of the elements on the right side of arr[3] are smaller.
- 0 items on the right side of arr[4] are smaller.
- In this method, we are making an array called countSmaller and storing the smaller elements on each element's right side will be the brute force method for solving this problem.
- For each element, the number of smaller items on the right side will be counted using nested for loops.
- Every time an element appears on the right side of the current element, we will increase the count. When the loop is complete, we will assign countSmaller[i] , the value of this count.
- The countSmaller array will be printed following the completion of both loops.
Method 1: Brute Force
C++ implementation:
Example
#include <iostream>
using namespace std;
// Function to count smaller elements on the right side of the array
void countSmallerElementsOnRightSide(int arr[], int n)
{
// To store the count for every element
int countSmaller[n] = {};
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
// If the condition is true, increment the corresponding index value in the countSmaller array
if (arr[i] > arr[j])
{
countSmaller[i]++;
}
}
}
// Print the countSmaller array
for (int i = 0; i < n; i++)
{
cout << countSmaller[i] << " ";
}
cout << endl;
}
int main()
{
int arr[] = {15, 10, 18, 5, 8, 11};
int n = 6;
countSmallerElementsOnRightSide(arr, n);
return 0;
}
Output:
Output
4 2 3 0 0 0
Method 2: Using Self-Balancing BST
- We will use self-balancing bst to solve this problem in O(N(log(n))
- We will traverse the array from left to right to add these components to the tree.
- We will initially compare the new key with the root when inserting it. The nodes of the root's left subtree would all be greater than the key if it were greater than the root.
- Therefore, we will increase the number of smaller items for the key being inserted by the size of the left subtree .
- We will recursively follow this process for all the nodes of the tree.
C++ implementation:
Example
// C++ code for counting smaller elements on the right side
#include <bits/stdc++.h>
using namespace std;
// AVL tree node
struct node
{
int key;
struct node *left;
struct node *right;
int height;
// to store the size of tree
int size;
};
// function to get the hieght of the tree
int height(struct node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// function to get the size of the tree
int size(struct node *N)
{
if (N == NULL)
return 0;
return N->size;
}
// function to get max of two numbers
int max(int a, int b)
{
return (a > b) ? a : b;
}
// function create a new node in the tree
struct node *newNode(int key)
{
struct node *node = (struct node *)
malloc(sizeof(struct node));
node->key = key;
node->left = NULL;
node->right = NULL;
// initially the new node
// is added on leaf
node->height = 1;
node->size = 1;
return (node);
}
// function to right rotate the subtree rooted with r
struct node *rightRotate(struct node *r)
{
struct node *x = r->left;
struct node *y = x->right;
// perform the rotation
x->right = r;
r->left = y;
// update the heights
r->height = max(height(r->left), height(r->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
// update the size
r->size = size(r->left) + size(r->right) + 1;
x->size = size(x->left) + size(x->right) + 1;
// return the root
return x;
}
// function to right rotate the subtree rooted with r
struct node *leftRotate(struct node *r)
{
struct node *x = r->right;
struct node *y = x->left;
// perform the rotation
x->left = r;
r->right = y;
// update the heights
r->height = max(height(r->left), height(r->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
// update the size
r->size = size(r->left) + size(r->right) + 1;
x->size = size(x->left) + size(x->right) + 1;
// return the root
return x;
}
// function to get the balance factor of node N
int getBalance(struct node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// function to insert a new key in the tree rooted with the node
// also updates the count of smaller elements for the new key
struct node *insert(struct node *node, int key, int *count)
{
// 1. First perform the normal rotation
if (node == NULL)
return (newNode(key));
if (key < node->key)
node->left = insert(node->left, key, count);
else
{
node->right = insert(node->right, key, count);
// to update the count of smaller elments for the key
*count = *count + size(node->left) + 1;
}
// 2. Now, update the hieght and size of the ancestor node
node->height = max(height(node->left), height(node->right)) + 1;
node->size = size(node->left) + size(node->right) + 1;
// 3. After that, get the balance factor of the ancestor node
int balance = getBalance(node);
// if the node becomes unbalanced then,
// left left case
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// right right case
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// left right case
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// right left case
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// function to update the countSmaller[] array
void constructLowerArray(int arr[], int countSmaller[], int n)
{
struct node *root = NULL;
for (int i = 0; i < n; i++)
countSmaller[i] = 0;
// start from the rightmost element, and then insert
// all the elments one by one in the AVL tree and
// then get the count of the smaller elements
for (int i = n - 1; i >= 0; i--)
{
root = insert(root, arr[i], &countSmaller[i]);
}
}
// function the print the array
void printArray(int arr[], int size)
{
cout << endl;
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
}
// Driver code
int main()
{
int arr[] = {5, 3, 6, 1, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int *l = (int *)malloc(sizeof(int) * n);
constructLowerArray(arr, l, n);
printArray(l, n);
return 0;
}
Output:
Output
Input: arr[] = {5, 3, 6, 1, 9}
Output: 2 1 1 0 0
Method 3: BST with two additional fields
- Binary Search Tree will contain two additional fields, including: the elements on the left side of the node will be stored in one field, and their frequencies will be kept in the second field.
- These elements will be added to the tree by right-to-left traversing the array.
- The number of items that are less than the current ones will be calculated when the new key is inserted. The number of components to the left of the current node and their frequencies added together will be our only calculation in doing this.
- Once an element is in the proper position, we may calculate its sum.
- This procedure will be repeated for each node in the tree.
Program:
Example
#include <bits/stdc++.h>
using namespace std;
// BST node structure
struct Node
{
int val, count;
Node *left, *right;
// Constructor
Node(int num1, int num2)
{
this->left = this->right = NULL;
this->count = num2;
this->val = num1;
}
};
// Function to add a node
int addNode(Node *&root, int countSmaller, int value)
{
// Base case
if (root == NULL)
{
root = new Node(value, 0);
return countSmaller;
}
if (root->val < value)
{
return root->count + addNode(root->right, countSmaller + 1, value);
}
else
{
root->count++;
return addNode(root->left, countSmaller, value);
}
}
int main()
{
int arr[] = {12, 9, 14, 6, 8, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int ans[n] = {};
Node *root = NULL;
for (int i = n - 1; i >= 0; i--)
ans[i] = addNode(root, 0, arr[i]);
for (int i = 0; i < n; i++)
cout << ans[i] << " ";
return 0;
}
Output:
Output
4 2 4 1 1 0
Conclusion:
In this tutorial, we addressed the challenge of tallying smaller objects located on the right side. We explored three strategies to tackle this issue: the brute force approach, a self-balancing binary search tree (BST), and finally, an alternative optimal method that utilizes a BST with two additional fields.
