Inversions in an array
Interview Question 51. Inversions in an Array Given two numbers in an array, if the earlier number is greater than the later one, the two numbers form an inversion. Given an array, find the total number of inversions in it.
Example 1:
Input: [7,5,6,4]
Output: 5
Constraints: 0 <= array length <= 50000
Approach
Brute-force solution
Just scan it mindlessly
1class Solution {
2public:
3 int reversePairs(vector<int>& nums) {
4 if (nums.size() == 0)
5 return 0;
6 int sum = 0;
7 for (int i = 0; i < nums.size() - 1; ++i) {
8 for (int j = i+1; j < nums.size(); ++j) {
9 if (nums[i] > nums[j])
10 sum++;
11 }
12 }
13 return sum;
14 }
15};
Time complexity $O(n^2)$, space complexity $O(1)$
Time limit exceeded! Let’s think about a new algorithm.
Divide and Conquer
This problem has the classic hallmarks of divide and conquer:
- The left and right halves are independent of each other, so it can be split into two subproblems.
- The basic idea is: count the inversions in the left half + count the inversions in the right half + count the inversions that cross the boundary.
Define a function _reversePairs to implement divide and conquer; then the solution function is
1int _reversePairs(vector<int>& nums, int begin, int end);
2
3int reversePairs(vector<int>& nums) {
4 return _reversePairs(nums, 0, nums.size());
5}
Now let’s look inside the _reversePairs function.
Idea: count the inversions in the left half + count the inversions in the right half + count the inversions that cross the boundary, solved recursively.
- Base case for the recursion: begin >= end terminates it.
- Find the midpoint, recursively count the inversions on the left, recursively count the inversions on the right.
- Count the inversions that cross the boundary.
- Sum them up and return.
The core of the algorithm is handling the count of inversions that cross the boundary.
I noticed that both halves are unsorted. If they were sorted, we could speed up the cross-boundary inversion count.
That brings merge sort to mind, because merge sort leaves the left and right halves sorted. So let’s use merge sort to solve this problem.
The concrete idea: during the merge, we need to compare values from the left and right sequences.
1#include <vector>
2#include <iterator>
3#include <iostream>
4using std::vector;
5
6class Solution {
7public:
8 int reversePairs(vector<int>& nums) {
9 temp = new int[nums.size()];
10 return _reversePairs(nums, 0, nums.size()-1);
11 }
12
13 int _reversePairs(vector<int>& nums, int begin, int end) {
14
15 if (begin < end) {
16 int mid = (end - begin)/2 + begin;
17 int left_rp = _reversePairs(nums, begin, mid); // Already sorted
18 int right_rp = _reversePairs(nums, mid+1, end);
19 // After both sides finish executing, it is already sorted
20 int i = begin, j = mid+1, k = begin;
21 int grap_rp = 0;
22 while (i <= mid && j <= end) {
23 if (nums[i] <= nums[j]) {
24 temp[k++] = nums[i++];
25 grap_rp += j - mid - 1;
26 } else {
27 // nums[i] > nums[j]
28 temp[k++] = nums[j++];
29 }
30 }
31
32 // 1 3 5 7 9 <= mid
33 // 4 5 6 8 10
34 //
35 while (i <= mid) {
36 temp[k++] = nums[i++];
37 grap_rp += j - mid - 1;
38 }
39 while (j <= end) temp[k++] = nums[j++];
40 std::copy(temp+begin, temp+end+1, nums.begin()+begin);
41 // std::copy(temp+begin, temp+end+1, std::ostream_iterator<int>(std::cout, " "));
42 // std::cout << std::endl;
43 // std::cout << "left_rp: " << left_rp << " right_rp: " << right_rp << " grap_rp: " << grap_rp << endl;
44 return left_rp + right_rp + grap_rp;
45 } else {
46 return 0;
47 }
48
49 }
50private:
51 int *temp;
52};
After running it, the result is:
Runtime:
- 148 ms, beating 92.74% of users across all C++ submissions
- Memory usage: 47.1 MB, beating 100.00% of users across all C++ submissions
Solving with a hash
Build a hashtable to record the number of times the number x appears. So to count inversions, we compute the sum of the hashtable values for the current number v through the end n. This way we traverse the sequence once, giving a time complexity of $O(n\*K)$, where K is the maximum value (since if the hashtable is to hold all values, it must have an index for every value). If K is very large, the computational complexity is unacceptable. So we introduce discretization: sort the numbers in nums from smallest to largest, remove duplicates, then use a hashmap to index each number, with its index being 1~n. This brings the time complexity down to $O(n\*2)$, the same as the brute-force method, which is also unacceptable.
So to simplify the computation of the sum of the hashtable values, we introduce a Fenwick tree (binary indexed tree) to solve this problem, which can reduce the time complexity to $O(nlogn)$.
Fenwick tree (BIT)
For the specific definition and usage of a Fenwick tree, see my other article
The core of this method is a Fenwick tree + coordinate compression
Discretization
Discretization is used to handle the problem where using a Fenwick tree (binary indexed tree) can cause the hash array to become too long
1vector<int> vec_elem;
2std::copy(nums.begin(), nums.end(), std::back_insert_iterator(vec_elem));
3sort(vec_elem.begin(), vec_elem.end());
4// Remove duplicates
5vec_elem.erase(unique(vec_elem.begin(), vec_elem.end), vec_elem.end());
6// Discretization operation
7int count = 1; // Mark count
8unordered_map<int, int> hashmap;
9for (int elem : vec_elem) {
10 hashmap[elem] = count++;
11}
Convert a sequence of increasing numbers into labels from 1 to n
The discretization operation is only suitable for offline computation, not for online computation.
Fenwick tree
For a detailed explanation, see my Fenwick tree summary. Fenwick tree
Build a Fenwick tree to count, for each position, how many of the numbers before x are greater than the number at position x. The Fenwick tree records, at each index, the count of the number x.
1vector<int> t(n + 1);
2int ans = 0;
3for (int i = 0; i < nums.size(); ++i) {
4 add(hashmap[nums[i]], t);
5 ans += (i+1) - ask(hashmap[nums[i]], t); // forward number + reverse number = i+1
6}
7return ans;
All the code
- Runtime: 208 ms, beats 66.29% of users across all C++ submissions
- Memory usage: 61.1 MB, beats 100.00% of users across all C++ submissions
1#include <vector>
2#include <algorithm>
3#include <unordered_map>
4#include <iterator>
5
6using std::vector;
7using std::sort;
8using std::unique;
9using std::unordered_map;
10
11class Solution {
12public:
13 int lowbit(int x) {
14 return x & (-x);
15 }
16 void add(int x, vector<int>& t) {
17 int n = t.size() - 1;
18 for (; x <= n; x += lowbit(x)) t[x] += 1;
19 }
20 int ask(int x, vector<int>& t) {
21 int res = 0;
22 for (; x > 0; x -= lowbit(x)) res += t[x];
23 return res;
24 }
25 int reversePairs(vector<int>& nums) {
26 int n = nums.size();
27 // Discretization operation
28 vector<int> vec_elem;
29 std::copy(nums.begin(), nums.end(), std::back_insert_iterator(vec_elem));
30 sort(vec_elem.begin(), vec_elem.end()); // Remove duplicates
31 vec_elem.erase(unique(vec_elem.begin(), vec_elem.end()), vec_elem.end());
32 int count = 1; // Mark count
33 unordered_map<int, int> hashmap;
34 for (int elem : vec_elem) {
35 hashmap[elem] = count++;
36 }
37 vector<int> t(n + 1);
38 int ans = 0;
39 for (int i = 0; i < nums.size(); ++i) {
40 add(hashmap[nums[i]], t);
41 ans += (i+1) - ask(hashmap[nums[i]], t);
42 }
43 return ans;
44 }
45};