Given an integer array arr of size n. An inversion is a pair of indices (i, j) such that i < j and arr[i] > arr[j]. Return the total number of inversions in the array.
Example 1
Input: arr = [8, 4, 2, 1, 5, 3, 7, 6]
Output: 13
Explanation: The value 8 forms seven inversions with every later value. Other useful pairs include (4, 2), (4, 1), (4, 3), (5, 3), and (7, 6). Counting all valid pairs gives 13.
Example 2
Input: arr = [2, 2, 1, -1]
Output: 5
Explanation: The pair formed by the two equal 2 values is not an inversion because the condition is strict. The valid inversions are (2, 1), (2, -1), (2, 1), (2, -1), and (1, -1).
Brute Force Approach
Brute force checks the definition directly. For every left position, each later position is inspected. Whenever the left value is greater than the later value, that pair contributes one inversion.
This works because every valid inversion has exactly one left index and one right index. The same pair is counted once, and invalid pairs are skipped. The drawback is that every possible pair may need inspection.
Algorithm
Initialize the inversion count as
0.Treat each index as the left side of a possible pair.
Compare it with every index placed to its right.
Increase the count when the left value is strictly greater than the right value.
Move to the next left index after all later indices have been checked; the process terminates after the final index.
Return the count. Empty and single-element arrays naturally return
0because no pair can be formed.
Dry Run
Count Inversion
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the total number of inversions. long long countInversions(vector<int>& arr) { int n = arr.size(); long long inversions = 0; // Choose each position as the left side of a pair. for (int left = 0; left < n; left++) { // Check only positions that appear after the left index. for (int right = left + 1; right < n; right++) { // A pair is an inversion only when the left value is greater. if (arr[left] > arr[right]) { inversions++; } } } return inversions; }};// Driver codeint main() { vector<int> arr = {8, 4, 2, 1, 5, 3, 7, 6}; // instance for class Solution Solution sol; cout << sol.countInversions(arr) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n²), because every possible ordered pair of indices may be checked once.
Space Complexity: O(1), because only a constant number of variables is used.
Optimal Approach
Instead of comparing each pair separately, merge sort can count inversions while arranging values. The key observation appears while two already sorted halves are combined.
If the current right-half value is smaller than the current left-half value, it is also smaller than every remaining value in the left half. All those remaining left-half values form inversions with that one right-half value. This counts many pairs at once and keeps the total work close to sorting.
Algorithm
If the current range has zero or one element, return
0because no inversion exists inside it.Split the current range into two halves and count inversions inside each half recursively.
Merge the two sorted halves into a temporary array.
Copy the left value when it is not greater than the right value, because no cross inversion is formed.
Copy the right value when it is smaller, and add the number of remaining left-half elements to the count.
Copy leftover values back into the current range; recursion terminates after every range reaches size one, and the accumulated count is returned.
Dry Run
count inversion
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Merges two sorted ranges and returns their cross inversions. long long mergeAndCount(vector<int>& nums, int left, int mid, int right) { vector<int> merged; int first = left; int second = mid + 1; long long inversions = 0; // Combine both sorted halves and count cross inversions. while (first <= mid && second <= right) { // Choose the left value when it is not greater; otherwise the right value creates cross inversions. if (nums[first] <= nums[second]) { merged.push_back(nums[first]); first++; } else { inversions += mid - first + 1; merged.push_back(nums[second]); second++; } } // Copy any values still remaining in the left half. while (first <= mid) { merged.push_back(nums[first]); first++; } // Copy any values still remaining in the right half. while (second <= right) { merged.push_back(nums[second]); second++; } int mergedSize = merged.size(); // Move the sorted values back into the active range. for (int index = 0; index < mergedSize; index++) { nums[left + index] = merged[index]; } return inversions; } // Counts inversions while sorting the current range. long long mergeSort(vector<int>& nums, int left, int right) { // A range with zero or one value has no inversion. if (left >= right) { return 0; } int mid = left + (right - left) / 2; long long inversions = 0; // Count inversions inside the left half. inversions += mergeSort(nums, left, mid); // Count inversions inside the right half. inversions += mergeSort(nums, mid + 1, right); // Count inversions formed across the two sorted halves. inversions += mergeAndCount(nums, left, mid, right); return inversions; }public: // Returns the total number of inversions. long long countInversions(vector<int>& arr) { vector<int> nums = arr; // An empty or single-element array has no inversion. if (nums.size() <= 1) { return 0; } int n = nums.size(); return mergeSort(nums, 0, n - 1); }};// Driver codeint main() { vector<int> arr = {8, 4, 2, 1, 5, 3, 7, 6}; // instance for class Solution Solution sol; cout << sol.countInversions(arr) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n log n), because the array is divided into halves and each level performs linear merging work.
Space Complexity: O(n), because the merge process uses temporary storage and the solution counts on a copied array to preserve the input.
Interview follow-up Questions
Merge sort creates sorted halves. During merging, if a right-half value is smaller than a left-half value, it is smaller than every remaining value in that left half. That single decision counts several inversion pairs together.
Be the first to add a comment.