Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Count Inversions

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
676 upvotes
Asked in companies
MicrosoftInfosysZomato

Problem statement

For a given integer array/list 'ARR' of size 'N' containing all distinct values, find the total number of 'Inversions' that may exist.

An inversion is defined for a pair of integers in the array/list when the following two conditions are met.

A pair ('ARR[i]', 'ARR[j]') is said to be an inversion when:

1. 'ARR[i] > 'ARR[j]' 
2. 'i' < 'j'

Where 'i' and 'j' denote the indices ranging from [0, 'N').
Detailed explanation ( Input/output format, Notes, Images )
Input format :
The first line of input contains an integer 'N', denoting the size of the array.

The second line of input contains 'N' integers separated by a single space, denoting the elements of the array 'ARR'.
Output format :
Print a single line containing a single integer that denotes the total count of inversions in the input array.
Note:
You are not required to print anything, it has been already taken care of. Just implement the given function.  
Constraints :
1 <= N <= 10^5 
1 <= ARR[i] <= 10^9

Where 'ARR[i]' denotes the array element at 'ith' index.

Time Limit: 1 sec
Sample Input 1 :
3
3 2 1
Sample Output 1 :
3
Explanation of Sample Output 1:
We have a total of 3 pairs which satisfy the condition of inversion. (3, 2), (2, 1) and (3, 1).
Sample Input 2 :
5
2 5 1 3 4
Sample Output 2 :
4
Explanation of Sample Output 1:
We have a total of 4 pairs which satisfy the condition of inversion. (2, 1), (5, 1), (5, 3) and (5, 4).


Hints:
1. Start with the brute force approach.
2. Use a modified merge sort.
3. Iterate through the elements in sorted order and use a Fenwick tree to track the inversions.
Approaches (3)
Brute Force Approach

The steps are as follows:

 

  1. Initialize a ‘COUNT’ with 0 to keep track of the number of inversions
  2. Iterate over every element in the array in a linear fashion starting from 0.
  3. For every element, check all the elements ahead of the current element and check the condition.
    1. If the condition satisfies, increase the ‘COUNT’ by 1.
    2. Otherwise, move to the next iteration.
  4. Return the ‘COUNT’.
Time Complexity

O(N ^ 2), Where ‘N’ is the total number of elements in the array.

 

Since for every element, we iterate over the remaining elements on right side, which makes it polynomial time. Thus the time complexity will be O(N ^ 2).

Space Complexity

O(1).

 

Since constant space is used. Thus the space complexity will be O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Count Inversions
All tags
Sort by
Search icon

Interview problems

Easy C++ Solution | Nested For Loops

#include <bits/stdc++.h> 
long long getInversions(long long *arr, int n){
    int count = 0;

    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            	if(arr[i] > arr[j]) count++;
        }
    }

    return count;
}
9 views
0 replies
0 upvotes

Interview problems

Solution for Count Inversion having Time Complexity : O(N log N) and Space Complexity : O( N )

import java.util.*;
import java.io.*;

public class Solution {
    private static long mergeAndCount(long[] arr, int left, int mid, int right) {
        long[] leftArray = Arrays.copyOfRange(arr, left, mid + 1);
        long[] rightArray = Arrays.copyOfRange(arr, mid + 1, right + 1);

        int i = 0, j = 0;
        long count = 0;
        int k = left;

        while (i < leftArray.length && j < rightArray.length) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k++] = leftArray[i++];
            } else {
                arr[k++] = rightArray[j++];
                count += (leftArray.length - i); // Count inversions
            }
        }

        while (i < leftArray.length) {
            arr[k++] = leftArray[i++];
        }

        while (j < rightArray.length) {
            arr[k++] = rightArray[j++];
        }

        return count;
    }

    private static long mergeSortAndCount(long[] arr, int left, int right) {
        long count = 0;
        if (left < right) {
            int mid = (left + right) / 2;

            count += mergeSortAndCount(arr, left, mid);
            count += mergeSortAndCount(arr, mid + 1, right);
            count += mergeAndCount(arr, left, mid, right);
        }
        return count;
    }

    public static long getInversions(long arr[], int n) {
        return mergeSortAndCount(arr, 0, n - 1);
    }

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextLong();
        }
        System.out.println(getInversions(arr, n));
    }
}
14 views
0 replies
1 upvote

Interview problems

brute force approach.

#include <bits/stdc++.h> 

long long getInversions(long long *arr, int n){

    // Write your code here.

    long long count=0;

    for(int i=0;i<n;i++){

        for(int j=n-1;j>=0;j--){

            if((arr[i]>arr[j]) && i<j){

                count++;

            }

        }

    }

    return count;

}

20 views
0 replies
0 upvotes

Interview problems

Java Easy Solution

import java.util.* ;
import java.io.*; 
public class Solution {
    private static long merge(long arr[], int low, int mid, int high){
        ArrayList<Long> temp = new ArrayList<>();

        int left = low;
        int right = mid+1;

        long count = 0;

        while(left <= mid && right <= high){
            if(arr[left] <= arr[right]){
                temp.add(arr[left]);
                left++;
            } else {
                temp.add(arr[right]);
                count += (mid - left + 1);
                right++;
            }
        }

        while(left <= mid){
            temp.add(arr[left]);
            left++;
        }

        while(right <= high){
            temp.add(arr[right]);
            right++;
        }

        for(int i=low; i<=high; i++){
            arr[i] = temp.get(i - low);
        }

        return count;
    }
    private static long mergeSort(long arr[], int low, int high){
        long count = 0;
        if(low >= high) return count;
        
        int mid = (low + high) / 2;
        count += mergeSort(arr, low, mid);
        count += mergeSort(arr, mid+1, high);
        count += merge(arr, low, mid, high);

        return count;

    }
    public static long getInversions(long arr[], int n) {
        return mergeSort(arr, 0, n-1);
    }
}
32 views
0 replies
1 upvote

Interview problems

EASY C++ CODE with SORTING and BINARY SEARCH

Description of the Code

The function getInversions calculates the number of inversions in an array, where an inversion is defined as a pair of indices (i, j) such that i < j and arr[i] > arr[j].

Explanation:

Initialization:

  • A vector v is used to store a copy of the elements in the array. This is necessary to sort the elements while keeping the original order in the array.

Sorting:

  • The vector v is sorted to facilitate efficient binary search operations using lower_bound. Sorting helps in finding the number of elements smaller than the current element.

Counting Inversions:

  • For each element a in the original array, the code uses lower_bound on the sorted vector to find the position of a. This gives the count of elements in the sorted vector that are smaller than a.
  • This count is added to the ans variable, which keeps track of the number of inversions.
  • The element a is then removed from the sorted vector to ensure it is not counted again in subsequent iterations.

Returning the Result:

  • Finally, the total number of inversions is returned.

Complexity

  • Sorting the vector takes O(n log n) time.
  • For each of the n elements, lower_bound and erase are used, leading to a time complexity of O(n log n) in the worst case.
  • Overall, the complexity is O(n log n), which is efficient for large arrays.

Note: This code counts the inversions based on the sorted positions of elements. By removing elements from the vector after each iteration, it ensures that elements are not double-counted.

 

C++ CODE

 

 

 

 

#include <bits/stdc++.h> 
long long getInversions(long long *arr, int n) {
   // Initialize a vector to store elements of the array
   vector<long long> v;

   // Copy elements from the array into the vector
   for(int i = 0; i < n; i++) {
       v.push_back(arr[i]);
   }

   long long ans = 0;  // Variable to store the count of inversions

   // Sort the vector. This helps in finding the position of elements efficiently.
   sort(v.begin(), v.end());

   // Iterate over each element in the array to count inversions
   for (int i = 0; i < n; i++) {
       long long a = arr[i];

       // Find the position of the current element 'a' in the sorted vector 'v'
       auto it = lower_bound(v.begin(), v.end(), a);

       // Calculate the index of the element 'a' in the sorted vector
       int b = it - v.begin();

       // Add this index to the inversion count
       ans += b;

       // Remove the element from the sorted vector to prevent counting it again
       v.erase(v.begin() + b);
   }

   return ans;  // Return the total number of inversions
}
 

185 views
0 replies
0 upvotes

Interview problems

JAVA BEST SOLUTION || Count Inversions ||

import java.util.* ;

import java.io.*; 

public class Solution {

    public static long getInversions(long arr[], int n) {

        long count = sort(arr, 0, n-1);

        return count;

    }

    public static long sort(long arr[], int left, int right) {

        long count = 0;

        if (left >= right) {

            return count;

        }

        int mid = left + right >> 1;

        count += sort(arr, left, mid);

        count += sort(arr, mid + 1, right);

        count += merge(arr, left, mid, right);

        return count;

    }

    public static long merge(long[] arr, int left, int mid, int right) {

        int n1 = mid - left + 1;

        int n2 = right - mid;

        long[] leftArr = new long[n1];

        long[] rightArr = new long[n2];

        for (int i = 0; i < n1; i++) {

            leftArr[i] = arr[left + i];

        }

        for (int i = 0; i < n2; i++) {

            rightArr[i] = arr[mid + 1 + i];

        }

        int i = 0, j = 0, k = left,  count = 0;

        while (i < n1 && j < n2) {

            if (leftArr[i] < rightArr[j]) {

                arr[k] = leftArr[i];

                i++;

            } else {

                arr[k] = rightArr[j];

                count += n1 - i;

                j++;

            }

            k++;

        }

        while (i < leftArr.length) {

            arr[k] = leftArr[i];

            i++;

            k++;

        }

        while (j < rightArr.length) {

            arr[k] = rightArr[j];

            j++;

            k++;

        }

        return count;

    }

}

74 views
0 replies
0 upvotes

Interview problems

Java Easy to Understand Solution

import java.util.* ;

import java.io.*; 

public class Solution {

    public static long getInversions(long arr[], int n) {

        long count = sort(arr, 0, n-1);

        return count;

    }

 

    public static long sort(long arr[], int left, int right) {

        long count = 0;

 

        if (left >= right) {

            return count;

        }

 

        int mid = left + right >> 1;

 

        count += sort(arr, left, mid);

        count += sort(arr, mid + 1, right);

 

        count += merge(arr, left, mid, right);

 

        return count;

    }

 

    public static long merge(long[] arr, int left, int mid, int right) {

        int n1 = mid - left + 1;

        int n2 = right - mid;

 

        long[] leftArr = new long[n1];

        long[] rightArr = new long[n2];

 

        for (int i = 0; i < n1; i++) {

            leftArr[i] = arr[left + i];

        }

 

        for (int i = 0; i < n2; i++) {

            rightArr[i] = arr[mid + 1 + i];

        }

 

        int i = 0, j = 0, k = left,  count = 0;

 

        while (i < n1 && j < n2) {

            if (leftArr[i] < rightArr[j]) {

                arr[k] = leftArr[i];

                i++;

            } else {

                arr[k] = rightArr[j];

                count += n1 - i;

                j++;

            }

            k++;

        }

 

        while (i < leftArr.length) {

            arr[k] = leftArr[i];

            i++;

            k++;

        }

 

        while (j < rightArr.length) {

            arr[k] = rightArr[j];

            j++;

            k++;

        }

 

        return count;

    }

}

35 views
0 replies
0 upvotes

Interview problems

C++ simple TC:O(N^2) solution SC:O(1)

#include <bits/stdc++.h> 

long long getInversions(long long *arr, int n){

    // Write your

    int cnt=0;

    for(int i=0;i<n;i++)

    {

        for(int j=1;j<n;j++)

        {

          if (i < j) {

            if (arr[i] > arr[j])

              cnt++;

          }

        }

    }

    return cnt;

}

286 views
0 replies
0 upvotes

Interview problems

✅BETTER THAN 100%🔥MERGE SORT🔥

#include <bits/stdc++.h> 

int cnt=0;

void merge(vector<int> &arr,int low,int mid,int high){

    vector<int> temp;

    int left=low;

    int right=mid+1;

    

    while(left<=mid && right<=high){

        if(arr[left]<=arr[right]){

            temp.push_back(arr[left]);

            left++;

        }

        else{

            temp.push_back(arr[right]);

            cnt+=(mid-left+1);

            right++;

        }

    }

    while(left<=mid){

        temp.push_back(arr[left]);

        left++;

    }

    while(right<=high){

        temp.push_back(arr[right]);

        right++;

    }

 

    int idx=0;

    for(int i=low;i<=high;i++){

        arr[i]=temp[idx++];

    }

    

}

 

void mS(vector<int> &arr,int low,int high){

    if(low==high){

        return;

    }

    int mid=(low+high)/2;

    mS(arr,low,mid);

    mS(arr,mid+1,high);

    merge(arr,low,mid,high);

    

}

 

int getInversions(vector<int> &arr, int n){

    

    mS(arr,0,n-1);

    return cnt;

}

593 views
0 replies
1 upvote

Interview problems

how can we modified this code

#include <bits/stdc++.h> 

long long getInversions(long long *arr, int n){

    // Write your code here.

    long long count=0;

    for(int i=0;i<n;i++){

        for(int j=i+1;j<n;j++){

            if(i<j && arr[i]>arr[j]){

                count++;

            }

        }

    }

    return count;

}

146 views
0 replies
1 upvote
Full screen
Console