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:
- Start with an empty AVL tree. The tree has a property that every node stores the size of the subtree rooted with this node.
- Initialize a variable result or count as 0.
-
Iterate from array index 0 to n-1, and for every element in A[i], do the following:
- Insert A[i] in the AVL tree.
- When we insert A[i], elements from A[0] to A[i-1] are already in the AVL Tree.
- 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]).
- 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.