Problem Statement
Given an integer array nums. Return the number of inversions in the array.
Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.
- It indicates how close an array is to being sorted.
- A sorted array has an inversion count of 0.
- An array sorted in descending order has maximum inversion.
Examples
Example: 1
Input: nums = [2, 3, 7, 1, 3, 5]
Output: 5
Explanation:
The responsible indexes are:
nums[0], nums[3], values: 2 > 1 & indexes: 0 < 3
nums[1], nums[3], values: 3 > 1 & indexes: 1 < 3
nums[2], nums[3], values: 7 > 1 & indexes: 2 < 3
nums[2], nums[4], values: 7 > 3 & indexes: 2 < 4
nums[2], nums[5], values: 7 > 5 & indexes: 2 < 5Example: 2
Input: nums = [-10, -5, 6, 11, 15, 17]
Output: 0
Explanation: nums is sorted, hence no inversions present.Example: 3
Input: nums = [9, 5, 4, 2]
Output: 6
Explanation: The inversion pair are:
nums[0], nums[1], values: 9 > 5 & indexes: 0 < 1
nums[0], nums[2], values: 9 > 4 & indexes: 0 < 2
nums[0], nums[3], values: 9 > 2 & indexes: 0 < 3
nums[1], nums[2], values: 5 > 4 & indexes: 1 < 2
nums[1], nums[3], values: 5 > 2 & indexes: 1 < 3
nums[2], nums[3], values: 4 > 2 & indexes: 2 < 3Different Approaches
1️⃣ Brute Force Approach
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.
Code:
#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;
}Complexity Analysis:
- Time Complexity:
O(N^2), for using 2 nested loops, whereNis the size of the array. - Space Complexity:
O(1), no extra space is used.
2️⃣ Merge Sort-based Approach
The Merge Sort-based approach for counting inversions combines the logic of merge sort with inversion counting. The core idea revolves around the concept that during the merge process, if an element from the left half is greater than an element from the right half, all the subsequent elements in the left half (since they are sorted) will also be greater than this element from the right half, forming inversions.
Approach:
- Recursive Splitting (Divide):
- Split the array into two halves recursively until you reach subarrays of size 1 (a single element array is trivially sorted and has no inversions).
- Merge and Count (Conquer):
- When merging two sorted halves:
- Compare the elements from both halves.
- If the element from the left half is smaller, place it in the merged array.
- If the element from the right half is smaller, it forms an inversion with every remaining element in the left half (because both halves are sorted, and all remaining elements in the left half are greater).
- Count how many elements in the left half are greater than this element from the right half (i.e.,
n1 - i, wheren1is the size of the left half, andiis the current index in the left half).
- When merging two sorted halves:
- Combine the Results:
- Sum up the inversions from the left half, the right half, and the merge step.
Steps:
In order to solve this, keep two pointers
iandj, whereiwill point to the first index ofarr1[]andjwill point to the first index ofarr2[]. Now in each iteration, do the following:- If
arr1[i]less than or equal toarr2[j]: These two elements cannot be a pair and so we will move the pointer i to the next position.
+-----+-----+-----+-----+ a1 = | 2 | 3 | 5 | 6 | +-----+-----+-----+-----+ 0 1 2 3 ^ | i +-----+-----+-----+-----+-----+ a2 = | 2 | 2 | 4 | 4 | 8 | +-----+-----+-----+-----+-----+ 0 1 2 3 4 ^ | j As, a1[i] == a2[j], so move 'i' pointer to the next position.Why we moved
ipointer:We know, that the given arrays are sorted. So, all the elements after the pointer
j, should be greater thana2[j]. Now, asa1[i]is smaller or equal toarr2[j], it is obvious thatarr1[i]will be smaller or equal to all the elements afterarr2[j]. We need a bigger value ofarr[i]to make a pair and so we move theipointer to the next position i.e., next bigger value.- If
If
arr1[i]greater thanarr2[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 thanarr2[j], all the elements afterarr1[i]will also be greater thanarr2[j]and so, those elements will also make pair witharr2[j]. So, the number of pairs added will ben1 - i(wheren1 = size of arr1[ ]). Now, we will move thejpointer to the next position.
+-----+-----+-----+-----+ a1 = | 2 | 3 | 5 | 6 | +-----+-----+-----+-----+ 0 1 2 3 ^ | i +-----+-----+-----+-----+-----+ a2 = | 2 | 2 | 4 | 4 | 8 | +-----+-----+-----+-----+-----+ 0 1 2 3 4 ^ | j As, a1[i] > a2[j], so elements after a[i] must be greater than a2[j] as both the arrays are sorted. So, total number of pairs = (size of a1) - i = 4 - 1 = 3 count += 3 Now we the 'j' pointer by 1.- These two elements can be a pair and so we will update the count of pairs. Now, here, we should observe that as
- 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:
Initialization
+-----+-----+-----+-----+
a1 = | 2 | 3 | 5 | 6 |
+-----+-----+-----+-----+
0 1 2 3
+-----+-----+-----+-----+-----+
a2 = | 2 | 2 | 4 | 4 | 8 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
count = 0i = 0, j = 0
+-----+-----+-----+-----+
a1 = | 2 | 3 | 5 | 6 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
+-----+-----+-----+-----+-----+
a2 = | 2 | 2 | 4 | 4 | 8 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
j
a1[i] == a2[j], so move i pointer to the next position
count = 0i = 1, j = 0
+-----+-----+-----+-----+
a1 = | 2 | 3 | 5 | 6 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
+-----+-----+-----+-----+-----+
a2 = | 2 | 2 | 4 | 4 | 8 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
j
a1[i] > a2[j], so add 'size of a1 - i' to count
and increment j.
count = 0 += size of a1 - i
= 0 += 4 - 1
= 0 + 3
= 3i = 1, j = 1
+-----+-----+-----+-----+
a1 = | 2 | 3 | 5 | 6 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
+-----+-----+-----+-----+-----+
a2 = | 2 | 2 | 4 | 4 | 8 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
j
a1[i] > a2[j], so add 'size of a1 - i' to count
and increment j.
count = 3 += size of a1 - i
= 3 += 4 - 1
= 3 + 3 = 6i = 1, j = 2
+-----+-----+-----+-----+
a1 = | 2 | 3 | 5 | 6 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
+-----+-----+-----+-----+-----+
a2 = | 2 | 2 | 4 | 4 | 8 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
j
a1[i] == a2[j], so increment i to the next position.
count = 6i = 2, j = 2
+-----+-----+-----+-----+
a1 = | 2 | 3 | 5 | 6 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
+-----+-----+-----+-----+-----+
a2 = | 2 | 2 | 4 | 4 | 8 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
j
a1[i] > a2[j], so add 'size of a1 - i' to count
and increment j.
count = 6 += size of a1 - i
= 6 += 4 - 2
= 6 + 2
= 8i = 2, j = 3
+-----+-----+-----+-----+
a1 = | 2 | 3 | 5 | 6 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
+-----+-----+-----+-----+-----+
a2 = | 2 | 2 | 4 | 4 | 8 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
j
a1[i] > a2[j], so add 'size of a1 - i' to count
and increment j.
count = 8 += size of a1 - i
8 += 4 - 2
8 + 2 = 10i = 2, j = 4
+-----+-----+-----+-----+
a1 = | 2 | 3 | 5 | 6 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
+-----+-----+-----+-----+-----+
a2 = | 2 | 2 | 4 | 4 | 8 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
j
a1[i] < a2[j], so increment i to the next position.
count = 10i = 3, j = 4
+-----+-----+-----+-----+
a1 = | 2 | 3 | 5 | 6 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
+-----+-----+-----+-----+-----+
a2 = | 2 | 2 | 4 | 4 | 8 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
j
a1[i] < a2[j], so increment i to the next position.
count = 10i = 4, j = 4 (Loop Termination)
+-----+-----+-----+-----+
a1 = | 2 | 3 | 5 | 6 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
+-----+-----+-----+-----+-----+
a2 = | 2 | 2 | 4 | 4 | 8 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
j
Since i has exceeds the a1 bounds.
So loop will terminate.
count = 10
Return `count`Code:
#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;
}Complexity Analysis:
- Time Complexity:
O(N x logN), whereNis 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.