Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem
2.
Solution
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024

Count Inversions in an Array Using AVL Tree

Author GAZAL ARORA
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Prerequisites: AVL Trees

Problem

Given an array A of size n. Print the inversion count of that array. Assume all the elements in the array are unique.

Input: 

  • An integer n.
  • The next n lines contain the array elements.

 

Output: Print the inversion count of that array.

 

Inversion count for an array indicates how far (or close) it is from being sorted.

There is an inversion in an array A if A[i] > A[j] and i < j.

  • The inversion count is minimum, i.e., 0, if the array is sorted in increasing order. 
  • The inversion count is maximum, i.e., (n*(n-1))/2, when an array is sorted in decreasing order where n is the size of the array.

 

Example,

1.

Input: N = 5, A[] = {5, 4, 6, 7, 1}

Output: 5

Explanation: Array A has five inversions:

(5,4), (5,1), (4,1), (6,1), (7,1).

 

2.

Input: N = 6, A[] = {6, 5, 4, 3, 2}

Output: 10

Explanation: Array A has ten inversions:

(6,5), (6,4), (6,3), (6,2), (5,4), (5,3), (5,2), (4,3), (4,2), (3,2).

 

3.

Input: A[] = {1, 2, 3, 4, 6, 8}

Output: 0

Explanation: Array A has 0 inversions.

 

 


 

Alert Ninjas:  Don’t stop now! Enroll in the Competitive Programming course today. Learn the art of writing time and space-efficient code and compete in code competitions worldwide. 

 


 

Recommended: Try to solve it yourself before moving on to the solution.

Solution

Idea: The idea is to use a Self-Balancing Binary Search Tree, such as the Red-Black Tree or the AVL Tree, and augment it so that each node keeps track of the number of nodes in the right subtree.

Algorithm:

  1. Start with an empty AVL tree. The tree has a property that every node stores the size of the subtree rooted with this node.
  2. Initialize a variable result or count as 0.
  3. Iterate from array index 0 to n-1, and for every element in A[i], do the following:
    1. Insert A[i] in the AVL tree.
    2. When we insert A[i], elements from A[0] to A[i-1] are already in the AVL Tree.
    3. For insertion into the AVL Tree, traverse from root to a leaf by comparing every node with A[i]. If A[i] is smaller than the current node, increase the inversion count by 1+ the number of nodes in the right subtree of the current node (which is the count of all the greater elements on the left of A[i]).
  4. Return the count.

 

C++

#include<bits/stdc++.h>
using namespace std;

struct Node
{
    struct Node *left, *right;
    int key, height;
      // size of the subtree from this node.
    int size;
};

struct Node* newNode(int key)
{
    struct Node* newNode = new Node;
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->height = 1;
    newNode->size = 1;
    return newNode;
}

// A function to get the tree's height rooted at the node.
int height(struct Node *node)
{
    if (!node)
        return 0;
    return node->height;
}
 
// A function to get the size of the tree rooted at the node.
int size(struct Node *node)
{
    if (!node)
        return 0;
    return node->size;
}

// A function to right rotate the subtree rooted at the node.
struct Node *rightRotate(struct Node *node)
{
    struct Node *x = node->left;
    struct Node *y = x->right;

    // Perform the rotation.
    x->right = node;
    node->left = y;

      // Update the heights.
    node->height = max(height(node->right), height(node->left))+1;
    x->height = max(height(x->right) , height(x->left))+1;

     // Update the sizes.
    node->size = 1 + size(node->left) + size(node->right);
    x->size = 1 + size(x->left) + size(x->right);

    // Return the new root.
    return x;
}

// A function to left rotate the subtree rooted at node.
struct Node *leftRotate(struct Node *node)
{
    struct Node *x = node->right;
    struct Node *y = x->left;

    // Perform the rotation.
    x->left = node;
    node->right = y;

    // Update the heights.
    node->height = max(height(node->right), height(node->left))+1;
    x->height = max(height(x->right) , height(x->left))+1;

    // Update the sizes.
    node->size = 1 + size(node->left) + size(node->right);
    x->size = 1 + size(x->left) + size(x->right);

    // Return the new root.
    return x;
}

// Get the Balance factor of Node N.
int getBalance(struct Node *node)
{
    if (!node)
        return 0;
    return height(node->left) - height(node->right);
}

// Insert function for the insertions in AVL tree. 
struct Node* insert(struct Node* node, int key, int &count)
{
    if (!node)
        return(newNode(key));
 
    if (key < node->key)
    {
        node->left  = insert(node->left, key, count);
        count += + size(node->right) + 1;
    }
    else
        node->right = insert(node->right, key, count);
 
    // Update the height and the size of the ancestor nodes.
    node->height = max(height(node->left), height(node->right)) + 1;
    node->size = size(node->left) + size(node->right) + 1;
 
    int balance = getBalance(node);

    // Left Left.
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
 
    // Right Right.
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
        
    // Right Left.
    if (balance < -1 && key < node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
 
    // Left Right.
    if (balance > 1 && key > node->left->key)
    {
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
    return node;
}

// The function for inversion count.
int getInversions(int A[], int n)
{
    // Create an empty AVL Tree.
    struct Node *root = NULL;
    int count = 0; 

    for (int i=0; i <= n-1 ; i++)
    root = insert(root, A[i], count);

    return count;
}

int main()
{
    int n = 5;
    int A[] = {5, 4, 6, 7, 1};
    cout << "Number of inversions count in the array are : " << getInversions(A,n);
    return 0;
}

 

Input: A[] = {5, 4, 6, 7, 1}

Output: 

Time complexity: O(n*logn). Because there are n elements and insertion in an AVL tree takes O(logn) time, the time complexity becomes O(n*log n).

Space Complexity: O(n). Since an AVL tree was created here with max ‘n’ nodes, hence, O(n) extra space is required here.

Check out this problem - Count Inversions.

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

FAQs

  1. What is an AVL tree?
    An AVL tree (named after the inventors Adelson-Velsky and Landis) is a self-balancing binary search tree balanced to maintain O(log n) height.
     
  2. What is an inversion of an array?
    The array's inversion count indicates how far (or close) the array is from being sorted. There is an inversion in an array A if A[i] > A[j] and i < j.

Key Takeaways

In this article, we learned about the inversion counts for an array. We learned that the Inversion count indicates how far (or close) the array is from being sorted. Then we designed an algorithm for counting inversions in a given array using AVL Tree in O(n*logn).


You can use Coding Ninjas Studio to practice various DSA questions asked in many interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.

Previous article
Optimal Sequence for AVL Tree Insertion
Next article
Find the Minimum number of nodes in an AVL Tree
Live masterclass