Count Inversions

Intuition

The naive approach is pretty straightforward, which will use nested loops to solve this problem. The prerequisite is that the index i must be smaller than index j. So, fix i at one index, and with another loop say(j), which runs from i+1 to last index of the array, try to count the inversion pairs.

Approach

Iterate in array from 0 to N-1 to select the first element in the pair. As index j should be greater than index i, inside loop i, run another loop i.e. j from i+1 to N-1. Inside this second loop, check if arr[i] is greater than arr[j] i.e. if arr[i] and arr[j] can be an inversion pair. If it satisfy the condition, increase the count by 1.

Finally, return the count i.e. the number of such pairs.

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

class Solution {
public:
    // Function to find number of inversions in an array
    long long int numberOfInversions(vector<int>&nums) {
    
    //size of the array 
    int n = nums.size();
    
    // Count the number of pairs:
    long long int cnt = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            
            /*if nums[i] is greater than 
            nums[j], increase countby 1.*/
            if (nums[i] > nums[j]) cnt++;
            
        }
    }
    
    //return the count of inversions
    return cnt;

    }
};

int main() {
    vector<int> nums = {5, 4, 3, 2, 1};
    
    // Create an instance of Solution class
    Solution sol;

    long long int result = sol.numberOfInversions(nums);
    
    // Print the repeating and missing numbers found
    cout << "The number of inversions is: "
         << result << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to find number of inversions in an array
    public long numberOfInversions(int[] nums) {
        
        // Size of the array
        int n = nums.length;

        // Count the number of pairs
        long cnt = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                
                /* If nums[i] is greater than 
                nums[j], increase count by 1*/
                if (nums[i] > nums[j]) {
                    cnt++;
                }
            }
        }

        // Return the count of inversions
        return cnt;
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {5, 4, 3, 2, 1};
        
        // Create an instance of Solution class
        Solution sol = new Solution();

        long result = sol.numberOfInversions(nums);
        
        // Print the number of inversions found
        System.out.println("The number of inversions is: " + result);
    }
}
from typing import List

class Solution:
    # Function to find number of inversions in an array
     def numberOfInversions(self, nums: List[int]) -> int:
        
        # Size of the array
        n = len(nums)

        # Count the number of pairs
        cnt = 0

        for i in range(n):
            for j in range(i + 1, n):
                
                """ If nums[i] is greater than 
                nums[j], increase count by 1"""
                if nums[i] > nums[j]:
                    cnt += 1

        # Return the count of inversions
        return cnt

# Main function
if __name__ == "__main__":
    nums = [5, 4, 3, 2, 1]
    
    # Create an instance of Solution class
    sol = Solution()

    result = sol.numberOfInversions(nums)
    
    # Print the number of inversions found
    print(f"The number of inversions is: {result}")
class Solution {
    // Function to find number of inversions in an array
    numberOfInversions(nums) {
        
        // Size of the array
        let n = nums.length;

        // Count the number of pairs
        let cnt = 0;

        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                
                /* If nums[i] is greater than
                nums[j], increase count by 1*/
                if (nums[i] > nums[j]) {
                    cnt++;
                }
            }
        }

        // Return the count of inversions
        return cnt;
    }
}

const nums = [5, 4, 3, 2, 1];

//Create an instance of Solution class
const sol = new Solution();

let result = sol.numberOfInversions(nums);

// Print the number of inversions found
console.log(`The number of inversions is: ${result}`);

Complexity Analysis

Time Complexity: O(N²), for using 2 nested loops, where N is the size of the array.

Space Complexity: O(1), no extra space is used.

Intuition

The optimal solution uses the concept of merge sort algorithm to count the inversion pairs in an array. Try to break down the problem as finding the count of inversion pairs in two sorted arrays. Finally, combine the count and return it.

Approach

In order to solve this, keep two pointers i and j, where i will point to the first index of arr1[] and j will point to the first index of arr2[]. Now in each iteration, do the following:
- If arr1[i] less than or equal to arr2[j]: These two elements cannot be a pair and so we will move the pointer i to the next position.
Why we moved the i pointer: We know, that the given arrays are sorted. So, all the elements after the pointer j, should be greater than a2[j]. Now, as a1[i] is smaller or equal to arr2[j], it is obvious that arr1[i] will be smaller or equal to all the elements after arr2[j]. We need a bigger value of arr1[i] to make a pair and so we move the i pointer to the next position i.e. next bigger value.
If arr1[i] greater than arr2[j]: These two elements can be a pair and so we will update the count of pairs. Now, here, we should observe that as arr1[i] is greater than arr2[j], all the elements after arr1[i] will also be greater than arr2[j] and so, those elements will also make pair with arr2[j]. So, the number of pairs added will be n1-i (where n1 = size of arr1[ ]). Now, we will move the j pointer to the next position.

The steps of the merge() function are the following:

In the merge function, we will use a temp array to store the elements of the two sorted arrays after merging. Here, the range of the left array is low to mid and the range for the right half is mid+1 to high.
Now we will take two pointers left and right, where left starts from low and right starts from mid+1.
Using a while loop( while(left <= mid && right <= high)), we will select two elements, one from each half, and will consider the smallest one among the two. Then, we will insert the smallest element in the temp array.
After that, the left-out elements in both halves will be copied as it is into the temp array. Now, we will just transfer the elements of the temp array to the range low to high in the original array

Modifications in merge() and mergeSort():

In order to count the number of pairs, we will keep a count variable, cnt, initialized to 0 beforehand inside the merge().
While comparing a[left] and a[right] in the 3rd step of merge(), if a[left] > a[right], we will simply add this line: cnt += mid-left+1 (mid+1 = size of the left half)
Now, we will return this cnt from merge() to mergeSort(). Inside mergeSort(), we will keep another counter variable that will store the final answer. With this cnt, we will add the answer returned from mergeSort() of the left half, mergeSort() of the right half, and merge(). Finally, we will return this cnt, as our answer from mergeSort().

Dry Run

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

class Solution {
private:
    /* Merge function to count 
    inversions and merge sorted halves*/
    long long int merge(vector<int>& arr, int low, int mid, int high) {
        
        // Temporary array for merging
        vector<int> temp;
        
        // Starting indices of left and right halves
        int left = low;
        int right = mid + 1;

        // Count variable to count the pairs
        long long int cnt = 0;

        // Merge sorted halves into temp array
        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                
                temp.push_back(arr[left]);
                left++;
                
            } 
            else {
                temp.push_back(arr[right]);
                
                // Count inversions
                cnt += (mid - left + 1);
                
                right++;
            }
        }

        // Copy remaining elements of left half
        while (left <= mid) {
            temp.push_back(arr[left]);
            left++;
        }

        // Copy remaining elements of right half
        while (right <= high) {
            temp.push_back(arr[right]);
            right++;
        }

        /* Copy elements from temp 
        array back to original array*/
        for (int i = low; i <= high; i++) {
            arr[i] = temp[i - low];
        }
        
        //return the count of inversions
        return cnt;
    }
    
    // Merge sort function to recursively sort and count inversions
    long long int mergeSort(vector<int>& arr, int low, int high) {
        long long int cnt = 0;
        if (low < high) {
            int mid = low + (high - low) / 2;
            
            // Sort left half
            cnt += mergeSort(arr, low, mid);  
            
            // Sort right half
            cnt += mergeSort(arr, mid + 1, high); 
            
            // Merge and count inversions
            cnt += merge(arr, low, mid, high);  
        }
        return cnt;
    }
    
public:
    // Function to find number of inversions in an array
    long long int numberOfInversions(vector<int>& nums) {
        
        // Size of the array
        int n = nums.size();

        // Count the number of pairs
        return mergeSort(nums, 0, n - 1);
    }
};

int main() {
    vector<int> nums = {5, 4, 3, 2, 1};
    
    // Create an instance of Solution class
    Solution sol;

    long long result = sol.numberOfInversions(nums);
    
    // Print the number of inversions found
    cout << "The number of inversions are: " << result << endl;
    
    return 0;
}
class Solution {
    
    /* Merge function to count 
    inversions and merge sorted halves */
    private long merge(int[] arr, int low, int mid, int high) {
        
        // Temporary array for merging
        int[] temp = new int[high - low + 1];
        
        // Starting indices of left and right halves
        int left = low;
        int right = mid + 1;
        int index = 0;

        // Count variable to count the pairs
        long cnt = 0;

        // Merge sorted halves into temp array
        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                temp[index++] = arr[left++];
            } else {
                temp[index++] = arr[right++];
                
                // Count inversions
                cnt += (mid - left + 1);
            }
        }

        // Copy remaining elements of left half
        while (left <= mid) {
            temp[index++] = arr[left++];
        }

        // Copy remaining elements of right half
        while (right <= high) {
            temp[index++] = arr[right++];
        }

        /* Copy elements from temp 
        array back to original array */
        System.arraycopy(temp, 0, arr, low, high - low + 1);
        
        // Return the count of inversions
        return cnt;
    }

    // Merge sort function to recursively sort and count inversions
    private long mergeSort(int[] arr, int low, int high) {
        long cnt = 0;
        if (low < high) {
            int mid = low + (high - low) / 2;
            
            // Sort left half
            cnt += mergeSort(arr, low, mid);
            
            // Sort right half
            cnt += mergeSort(arr, mid + 1, high);
            
            // Merge and count inversions
            cnt += merge(arr, low, mid, high);
        }
        return cnt;
    }
    
    // Public function to find number of inversions in an array
    public long numberOfInversions(int[] nums) {
        
        // Size of the array
        int n = nums.length;

        // Count the number of pairs
        return mergeSort(nums, 0, n - 1);
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {5, 4, 3, 2, 1};

        // Create an instance of Solution class
        Solution sol = new Solution();

        long result = sol.numberOfInversions(nums);

        // Print the number of inversions found
        System.out.println("The number of inversions are: " + result);
    }
}
class Solution:
    
    # Merge function to count 
    # inversions and merge sorted halves
    def merge(self, arr, low, mid, high):
        
        # Temporary array for merging
        temp = []
        
        # Starting indices of left and right halves
        left = low
        right = mid + 1

        # Count variable to count the pairs
        cnt = 0

        # Merge sorted halves into temp array
        while left <= mid and right <= high:
            if arr[left] <= arr[right]:
                
                temp.append(arr[left])
                left += 1
                
            else:
                temp.append(arr[right])
                
                # Count inversions
                cnt += (mid - left + 1)
                
                right += 1

        # Copy remaining elements of left half
        while left <= mid:
            temp.append(arr[left])
            left += 1

        # Copy remaining elements of right half
        while right <= high:
            temp.append(arr[right])
            right += 1

        # Copy elements from temp 
        # array back to original array
        for i in range(low, high + 1):
            arr[i] = temp[i - low]
        
        # Return the count of inversions
        return cnt

    # Merge sort function to recursively sort and count inversions
    def mergeSort(self, arr, low, high):
        cnt = 0
        if low < high:
            mid = low + (high - low) // 2
            
            # Sort left half
            cnt += self.mergeSort(arr, low, mid)
            
            # Sort right half
            cnt += self.mergeSort(arr, mid + 1, high)
            
            # Merge and count inversions
            cnt += self.merge(arr, low, mid, high)
        return cnt
    
    # Function to find number of inversions in an array
    def numberOfInversions(self, nums):
        
        # Size of the array
        n = len(nums)

        # Count the number of pairs
        return self.mergeSort(nums, 0, n - 1)

if __name__ == "__main__":
    nums = [5, 4, 3, 2, 1]

    # Create an instance of Solution class
    sol = Solution()

    result = sol.numberOfInversions(nums)

    # Print the number of inversions found
    print(f"The number of inversions are: {result}")
class Solution {
    
    /* Merge function to count 
    inversions and merge sorted halves */
    merge(arr, low, mid, high) {
        
        // Temporary array for merging
        const temp = [];
        
        // Starting indices of left and right halves
        let left = low;
        let right = mid + 1;

        // Count variable to count the pairs
        let cnt = 0;

        // Merge sorted halves into temp array
        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                
                temp.push(arr[left]);
                left++;
                
            } else {
                temp.push(arr[right]);
                
                // Count inversions
                cnt += (mid - left + 1);
                
                right++;
            }
        }

        // Copy remaining elements of left half
        while (left <= mid) {
            temp.push(arr[left]);
            left++;
        }

        // Copy remaining elements of right half
        while (right <= high) {
            temp.push(arr[right]);
            right++;
        }

        /* Copy elements from temp 
        array back to original array */
        for (let i = low; i <= high; i++) {
            arr[i] = temp[i - low];
        }
        
        // Return the count of inversions
        return cnt;
    }

    // Merge sort function to recursively sort and count inversions
    mergeSort(arr, low, high) {
        let cnt = 0;
        if (low < high) {
            const mid = low + Math.floor((high - low) / 2);
            
            // Sort left half
            cnt += this.mergeSort(arr, low, mid);  
            
            // Sort right half
            cnt += this.mergeSort(arr, mid + 1, high); 
            
            // Merge and count inversions
            cnt += this.merge(arr, low, mid, high);  
        }
        return cnt;
    }
    
    // Function to find number of inversions in an array
    numberOfInversions(nums) {
        
        // Size of the array
        const n = nums.length;

        // Count the number of pairs
        return this.mergeSort(nums, 0, n - 1);
    }
}

const nums = [5, 4, 3, 2, 1];

// Create an instance of Solution class
const sol = new Solution();

const result = sol.numberOfInversions(nums);

// Print the number of inversions found
console.log("The number of inversions are: " + result);

Complexity Analysis

Time Complexity: O(NxlogN), where N is size of the given array. We are not changing the merge sort algorithm except by adding a variable to it. So, the time complexity is as same as the merge sort.

Space Complexity: O(N), in the merge sort there is use a temporary array to store elements in sorted order.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Complexity Analysis

Intuition

Approach

Dry Run

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts