Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Implementation in C++
2.1.1.
Complexity Analysis
3.
Optimal Approach Using Self Balancing Bst
3.1.
Implementation in C++
3.1.1.
Complexity Analysis
4.
Optimal Approach Using BST with two extra fields
4.1.
Implementation in C++
4.1.1.
Complexity Analysis
5.
FAQs
6.
Key takeaways
Last Updated: Mar 27, 2024

Counting smaller elements on the right side

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction 

This blog will discuss the solution to the problem of counting smaller elements on the right side. 

Problem Statement

We are given an unsorted array arr[] which consists of distinct integers, and the size of the array is N. Our task is to construct another array countSmaller[] where countSmaller[i] will represent the count of elements that are less than the arr[i] and are present on the right side of the array. 

Sample Examples

Example 1:

Input:
N=3, arr[] = {3, 2, 1}

Output: 
{2, 1, 0}

Explanation:
For arr[0], two elements on the right side are smaller.
For arr[1], one element on the right side is smaller.
For arr[2], 0 elements on the right side are smaller.

 

Example 2:

Input:
N=5, arr[] = {7, 1, 5, 2, 10}

Output:
{3, 0, 0, 2, 0}

Explanation:
For arr[0], three elements on the right side are smaller.
For arr[1], 0 elements on the right side is smaller.
For arr[2], 0 elements on the right side are smaller.
For arr[3], 2 elements on the right side are smaller.
For arr[4], 0 elements on the right side are smaller.

 

Brute Force Approach

  1. The brute force approach for this problem is to make an array named countSmaller[] where we will store the smaller elements on the right side for every element of the array.
  2. We will use nested for loops to count the number of smaller elements on the right side for every element.
  3. We will increment the count whenever we see any element present on the right side of the current element, and when the loop ends, we will assign countSmaller[i], The value of this count.
  4. After both the loops are over, we will print the countSmaller array.

Implementation in C++

// C++ code for counting smaller elements on the right side
#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 condition is true then we will increment the
            // corresponding index value in the countSmaller arrray
            if (arr[i] > arr[j])
            {
                countSmaller[i]++;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << countSmaller[i] << " ";
    }
    cout << endl;
}

// Driver code
int main()
{
    int arr[] = {19, 1, 5, 20, 21, 7, 9, 4, 10, 30};
    int n = 10;
    countSmallerElementsOnRightSide(arr, n);
    return 0;
}

 

Output:

Input: arr[] = {19, 1, 5, 20, 21, 7, 9, 4, 10, 30}
Output: 6 0 1 4 4 1 1 0 0 0

 

Complexity Analysis

Time Complexity: O(N²)

Since we are using two nested for loop in this approach, therefore the time complexity will be O(N²)

Space Complexity: O(1)

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimal Approach Using Self Balancing Bst

  1. We will use self-balancing bst to solve this problem in O(N(log(n)) time. 
  2. We will traverse the array from left to right and insert these elements into the tree.
  3. While inserting the new key, we will first compare the new key with the root. If the key is greater than the root, it would be greater than all the nodes of the left subtree of the root. 
  4. So we will add the size of the left subtree to the count of smaller elements for the key being inserted. 
  5. We will recursively follow this process for all the nodes of the tree.

Implementation in C++

// 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:

Input: arr[] = {5, 3, 6, 1, 9}  
Output: 2 1 1 0 0 

 

Complexity Analysis

Time Complexity: O(N(log(N))

Insertion of N elements in bst causes O(N(log(N)) time complexity.

Space Complexity: O(N)

Creation of bst of size N takes O(N) time.

Optimal Approach Using BST with two extra fields

  1.  Binary Search Tree which will have two extra fields:
  2. One field will hold the elements on the left side of the node, and the second field will store the frequency of elements.
  3. We will traverse the array from right to left and insert these elements into the tree.
  4. While inserting the new key, we will compute the number of lesser elements than the current ones. We will do this by simply computing the sum of the frequencies of the elements and the number of elements to the left side of the current node.
  5. Once we place an element to its correct position, we can its sum value. 
  6. We will recursively follow this process for all the nodes of the tree.

Implementation in C++

// C++ code for counting smaller elements on the right side
#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);
    }
}

// Driver code
int main()
{
    int arr[] = {6, 1, 4, 9, 5, 7};
    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:

Input: arr[] = {6, 1, 4, 9, 5, 7}  
Output: 3 0 0 2 0 0  

 

Complexity Analysis

Time Complexity: O(N(log(N))

Insertion of N elements in bst causes O(N(log(N)) time complexity.

Space Complexity: O(N)

Creation of bst of size N takes O(N) time.

Check out this problem - Next Smaller Element

FAQs

  1. What is the searching time complexity in a BST?
    On average, the worst-case time complexity is O(Logn), and in the worst case, it’s O(n), i.e., the case of a skewed BST where ‘n’ is the number of nodes in the BST.  
     
  2. What are leave nodes in a binary tree?
    Leave nodes of a tree are those nodes that don’t have any children, and both the pointers of the nodes point to null.
     
  3. What is level order traversal?
    A traversal that always travels depending on the tree's level is known as a Level Order Traversal. From the root node, this traversal initially visits the nodes corresponding to Level 0, then Level 1, and so on.

Key takeaways

This article discussed the problem of counting smaller elements on the right side. We have discussed three approaches to this problem: the brute force approach, the second one is an optimal approach using self-balancing bst, and the last one is also optimal, but it uses bst with two extra fields. We have also discussed the time complexities of all the approaches.

You can try these additional problems:

  1. Insert a node in BST
  2. Search a node in BST
  3. BST from preorder
  4. Maximum Sum Path In BST

Until then, Keep Learning and Keep Coding.


Previous article
Sort the big sized array where there are many repetitions of elements
Next article
Suffix Trees (Implementation - Brute Force)
Live masterclass