493. Reverse Pairs

  • 17.7%

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2* nums[j].

You need to return the number of important reverse pairs in the given array.

1
2
3
4
Example1:

Input: [1,3,2,3,1]
Output: 2
1
2
3
4
Example2:

Input: [2,4,3,5,1]
Output: 3

Note:

  1. The length of the given array will not exceed 50,000.
  2. All the numbers in the input array are in the range of 32-bit integer.

cpp


https://discuss.leetcode.com/topic/78993/c-with-iterators

C++ with iterators

Just a mergesort solution, but using iterators (instead of indexes) and inplace_merge.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int sort_and_count(vector<int>::iterator begin, vector<int>::iterator end) {
if (end - begin <= 1)
return 0;
auto mid = begin + (end - begin) / 2;
int count = sort_and_count(begin, mid) + sort_and_count(mid, end);
for (auto i = begin, j = mid; i != mid; ++i) {
while (j != end and *i > 2L * *j)
++j;
count += j - mid;
}
inplace_merge(begin, mid, end);
return count;
}

int reversePairs(vector<int>& nums) {
return sort_and_count(nums.begin(), nums.end());
}
};

https://discuss.leetcode.com/topic/78953/c-solution-using-merge-sort

C++ Solution using merge sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
private:
int count;

void checkCount(vector<int>& nums, int start, int mid, int end){

// two pointers;
int l = start, r = mid + 1;
while(l <= mid && r <= end){
if((long)nums[l] > (long) 2 * nums[r]){
count += (mid - l + 1);
r++;
}else{
l++;
}
}
// worst case might be nlog(n)
sort(nums.begin() + start, nums.begin() + end + 1);
return;



//every step sort
}
void mergeSort(vector<int>& nums, int start, int end){
if(start == end) return;

int mid = (start + end)/2;
mergeSort(nums,start, mid);
mergeSort(nums,mid+1,end);

checkCount(nums,start,mid,end);
return;

}
public:
int reversePairs(vector<int>& nums) {
if(!nums.size())return 0;
count = 0;
mergeSort(nums,0,nums.size()-1);
return count;
}
};

python


https://discuss.leetcode.com/topic/78980/well-explained-o-nlogn-python-solution-based-on-mergesort

Well explained O(nlogn) Python Solution based on mergesort

Count “important reverse pairs” while doing mergesort:

When we’re doing mergesort, original index of elements in left part (smaller side), i, must less than those in right part, j.

Simply compare nums[i] and 2* nums[j] and sum them up.

Note that those partial lists induced during mergesort here are generated by sorted(), instead of building it one by one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
def __init__(self):
self.cnt = 0
def reversePairs(self, nums):
def msort(lst):
# merge sort body
L = len(lst)
if L <= 1: # base case
return lst
else: # recursive case
return merger(msort(lst[:int(L/2)]), msort(lst[int(L/2):]))
def merger(left, right):
# merger
l, r = 0, 0 # increase l and r iteratively
while l < len(left) and r < len(right):
if left[l] <= 2*right[r]:
l += 1
else:
self.cnt += len(left)-l # add here
r += 1
return sorted(left+right) # I can't avoid TLE without timsort...

msort(nums)
return self.cnt

java


https://discuss.leetcode.com/topic/78933/very-short-and-clear-mergesort-bst-java-solutions

Very Short and Clear MergeSort & BST Java Solutions

MergeSort

Explanation: In each round, we divide our array into two parts and sort them. So after “int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e); “, the left part and the right part are sorted and now our only job is to count how many pairs of number (leftPart[i], rightPart[j]) satisfies leftPart[i] <= 2* rightPart[j].
For example,
left: 4 6 8 right: 1 2 3
so we use two pointers to travel left and right parts. For each leftPart[i], if j<=e && nums[i]/2.0 > nums[j], we just continue to move j to the end, to increase rightPart[j], until it is valid. Like in our example, left’s 4 can match 1 and 2; left’s 6 can match 1, 2, 3, and left’s 8 can match 1, 2, 3. So in this particular round, there are 8 pairs found, so we increases our total by 8.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int reversePairs(int[] nums) {
return mergeSort(nums, 0, nums.length-1);
}
private int mergeSort(int[] nums, int s, int e){
if(s>=e) return 0;
int mid = s + (e-s)/2;
int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e);
for(int i = s, j = mid+1; i<=mid; i++){
while(j<=e && nums[i]/2.0 > nums[j]) j++;
cnt += j-(mid+1);
}
Arrays.sort(nums, s, e+1);
return cnt;
}
}

Or:
Because left part and right part are sorted, you can replace the Arrays.sort() part with a actual merge sort process. The previous version is easy to write, while this one is faster.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
int[] helper;
public int reversePairs(int[] nums) {
this.helper = new int[nums.length];
return mergeSort(nums, 0, nums.length-1);
}
private int mergeSort(int[] nums, int s, int e){
if(s>=e) return 0;
int mid = s + (e-s)/2;
int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e);
for(int i = s, j = mid+1; i<=mid; i++){
while(j<=e && nums[i]/2.0 > nums[j]) j++;
cnt += j-(mid+1);
}
//Arrays.sort(nums, s, e+1);
myMerge(nums, s, mid, e);
return cnt;
}

private void myMerge(int[] nums, int s, int mid, int e){
for(int i = s; i<=e; i++) helper[i] = nums[i];
int p1 = s;//pointer for left part
int p2 = mid+1;//pointer for rigth part
int i = s;//pointer for sorted array
while(p1<=mid || p2<=e){
if(p1>mid || (p2<=e && helper[p1] >= helper[p2])){
nums[i++] = helper[p2++];
}else{
nums[i++] = helper[p1++];
}
}
}
}

BST
BST solution is no longer acceptable, because it’s performance can be very bad, O(n^2) actually, for extreme cases like [1,2,3,4……49999], due to the its unbalance, but I am still providing it below just FYI.
We build the Binary Search Tree from right to left, and at the same time, search the partially built tree with nums[i]/2.0. The code below should be clear enough.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Solution {
public int reversePairs(int[] nums) {
Node root = null;
int[] cnt = new int[1];
for(int i = nums.length-1; i>=0; i--){
search(cnt, root, nums[i]/2.0);//search and count the partially built tree
root = build(nums[i], root);//add nums[i] to BST
}
return cnt[0];
}

private void search(int[] cnt, Node node, double target){
if(node==null) return;
else if(target == node.val) cnt[0] += node.less;
else if(target < node.val) search(cnt, node.left, target);
else{
cnt[0]+=node.less + node.same;
search(cnt, node.right, target);
}
}

private Node build(int val, Node n){
if(n==null) return new Node(val);
else if(val == n.val) n.same+=1;
else if(val > n.val) n.right = build(val, n.right);
else{
n.less += 1;
n.left = build(val, n.left);
}
return n;
}

class Node{
int val, less = 0, same = 1;//less: number of nodes that less than this node.val
Node left, right;
public Node(int v){
this.val = v;
}
}
}

Similar to this https://leetcode.com/problems/count-of-smaller-numbers-after-self/. But the main difference is: here, the number to add and the number to search are different (add nums[i], but search nums[i]/2.0), so not a good idea to combine build and search together.


https://discuss.leetcode.com/topic/79227/general-principles-behind-problems-similar-to-reverse-pairs

General principles behind problems similar to “Reverse Pairs”

It looks like a host of solutions are out there (BST-based, BIT-based, Merge-sort-based). Here I’d like to focus on the general principles behind these solutions and its possible application to a number of similar problems.

The fundamental idea is very simple: break down the array and solve for the subproblems.

A breakdown of an array naturally reminds us of subarrays. To smoothen our following discussion, let’s assume the input array is nums, with a total of n elements. Let nums[i, j] denote the subarray starting from index i to index j (both inclusive), T(i, j) as the same problem applied to this subarray (for example, for Reverse Pairs, T(i, j) will represent the total number of important reverse pairs for subarray nums[i, j]).

With the definition above, it’s straightforward to identify our original problem as T(0, n - 1). Now the key point is how to construct solutions to the original problem from its subproblems. This is essentially equivalent to building recurrence relations for T(i, j). Since if we can find solutions to T(i, j) from its subproblems, we surely can build solutions to larger subarrays until eventually the whole array is spanned.

While there may be many ways for establishing recurrence relations for T(i, j), here I will only introduce the following two common ones:

  1. T(i, j) = T(i, j - 1) + C, i.e., elements will be processed sequentially and C denotes the subproblem for processing the last element of subarray nums[i, j]. We will call this sequential recurrence relation.
  2. T(i, j) = T(i, m) + T(m + 1, j) + C where m = (i+j)/2, i.e., subarray nums[i, j] will be further partitioned into two parts and C denotes the subproblem for combining the two parts. We will call this partition recurrence relation.

For either case, the nature of the subproblem C will depend on the problem under consideration, and it will determine the overall time complexity of the original problem. So usually it’s crucial to find efficient algorithm for solving this subproblem in order to have better time performance. Also pay attention to possibilities of overlapping subproblems, in which case a dynamic programming (DP) approach would be preferred.

Next, I will apply these two recurrence relations to this problem “Reverse Pairs” and list some solutions for your reference.

I – Sequential recurrence relation

Again we assume the input array is nums with n elements and T(i, j) denotes the total number of important reverse pairs for subarray nums[i, j]. For sequential recurrence relation, we can set i = 0, i.e., the subarray always starts from the beginning. Therefore we end up with:

T(0, j) = T(0, j - 1) + C

where the subproblem C now becomes “find the number of important reverse pairs with the first element of the pair coming from subarray nums[i, j - 1] while the second element of the pair being nums[j]”.

Note that for a pair (p, q) to be an important reverse pair, it has to satisfy the following two conditions:

  1. p < q: the first element must come before the second element;
  2. nums[p] > 2 * nums[q]: the first element has to be greater than twice of the second element.

For subproblem C, the first condition is met automatically; so we only need to consider the second condition, which is equivalent to searching for all elements within subarray nums[i, j - 1] that are greater than twice of nums[j].

The straightforward way of searching would be a linear scan of the subarray, which runs at the order of O(j). From the sequential recurrence relation, this leads to the naive O(n^2) solution.

To improve the searching efficiency, a key observation is that the order of elements in the subarray does not matter, since we are only interested in the total number of important reverse pairs. This suggests we may sort those elements and do a binary search instead of a plain linear scan.

If the searching space (formed by elements over which the search will be done) is “static” (it does not vary from run to run), placing the elements into an array would be perfect for us to do the binary search. However, this is not the case here. After the j-th element is processed, we need to add it to the searching space so that it becomes searchable for later elements, which renders the searching space expanding as more and more elements are processed.

Therefore we’d like to strike a balance between searching and insertion operations. This is where data structures like binary search tree (BST) or binary indexed tree (BIT) prevail, which offers relatively fast performance for both operations.

1. BST-based solution

we will define the tree node as follows, where val is the node value and cnt is the total number of elements in the subtree rooted at current node that are greater than or equal to val:

1
2
3
4
5
6
7
8
9
class Node {
int val, cnt;
Node left, right;

Node(int val) {
this.val = val;
this.cnt = 1;
}
}

The searching and insertion operations can be done as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private int search(Node root, long val) {
if (root == null) {
return 0;
} else if (val == root.val) {
return root.cnt;
} else if (val < root.val) {
return root.cnt + search(root.left, val);
} else {
return search(root.right, val);
}
}

private Node insert(Node root, int val) {
if (root == null) {
root = new Node(val);
} else if (val == root.val) {
root.cnt++;
} else if (val < root.val) {
root.left = insert(root.left, val);
} else {
root.cnt++;
root.right = insert(root.right, val);
}

return root;
}

And finally the main program, in which we will search for all elements no less than twice of current element plus 1 (converted to long type to avoid overflow) while insert the element itself into the BST.

Note: this homemade BST is not self-balanced and the time complexity can go as bad as O(n^2) (in fact you will get TLE if you copy and paste the solution here). To guarantee O(nlogn) performance, use one of the self-balanced BST’s (e.g. Red-black tree, AVL tree, etc.).

1
2
3
4
5
6
7
8
9
10
11
public int reversePairs(int[] nums) {
int res = 0;
Node root = null;

for (int ele : nums) {
res += search(root, 2L * ele + 1);
root = insert(root, ele);
}

return res;
}

2. BIT-based solution

For BIT, the searching and insertion operations are:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int search(int[] bit, int i) {
int sum = 0;

while (i < bit.length) {
sum += bit[i];
i += i & -i;
}

return sum;
}

private void insert(int[] bit, int i) {
while (i > 0) {
bit[i] += 1;
i -= i & -i;
}
}

And the main program, where again we will search for all elements greater than twice of current element while insert the element itself into the BIT. For each element, the “index” function will return its index in the BIT. Unlike the BST-based solution, this is guaranteed to run at O(nlogn).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int reversePairs(int[] nums) {
int res = 0;
int[] copy = Arrays.copyOf(nums, nums.length);
int[] bit = new int[copy.length + 1];

Arrays.sort(copy);

for (int ele : nums) {
res += search(bit, index(copy, 2L * ele + 1));
insert(bit, index(copy, ele));
}

return res;
}

private int index(int[] arr, long val) {
int l = 0, r = arr.length - 1, m = 0;

while (l <= r) {
m = l + ((r - l) >> 1);

if (arr[m] >= val) {
r = m - 1;
} else {
l = m + 1;
}
}

return l + 1;
}

More explanation for the BIT-based solution:

  1. We want the elements to be sorted so there is a sorted version of the input array which is copy.
  2. The bit is built upon this sorted array. Its length is one greater than that of the copy array to account for the root.
  3. Initially the bit is empty and we start doing a sequential scan of the input array. For each element being scanned, we first search the bit to find all elements greater than twice of it and add the result to res. We then insert the element itself into the bit for future search.
  4. Note that conventionally searching of the bit involves traversing towards the root from some index of the bit, which will yield a predefined running total of the copy array up to the corresponding index. For insertion, the traversing direction will be opposite and go from some index towards the end of the bit array.
  5. For each scanned element of the input array, its searching index will be given by the index of the first element in the copy array that is greater than twice of it (shifted up by 1 to account for the root), while its insertion index will be the index of the first element in the copy array that is no less than itself (again shifted up by 1). This is what the index function is for.
  6. For our case, the running total is simply the number of elements encountered during the traversal process. If we stick to the convention above, the running total will be the number of elements smaller than the one at the given index, since the copy array is sorted in ascending order. However, we’d actually like to find the number of elements greater than some value (i.e., twice of the element being scanned), therefore we need to flip the convention. This is what you see inside the search and insert functions: the former traversing towards the end of the bit while the latter towards the root.

II – Partition recurrence relation

For partition recurrence relation, setting i = 0, j = n - 1, m = (n-1)/2, we have:

T(0, n - 1) = T(0, m) + T(m + 1, n - 1) + C

where the subproblem C now reads “find the number of important reverse pairs with the first element of the pair coming from the left subarray nums[0, m] while the second element of the pair coming from the right subarray nums[m + 1, n - 1]”.

Again for this subproblem, the first of the two aforementioned conditions is met automatically. As for the second condition, we have as usual this plain linear scan algorithm, applied for each element in the left (or right) subarray. This, to no surprise, leads to the O(n^2) naive solution.

Fortunately the observation holds true here that the order of elements in the left or right subarray does not matter, which prompts sorting of elements in both subarrays. With both subarrays sorted, the number of important reverse pairs can be found in linear time by employing the so-called two-pointer technique: one pointing to elements in the left subarray while the other to those in the right subarray and both pointers will go only in one direction due to the ordering of the elements.

The last question is which algorithm is best here to sort the subarrays. Since we need to partition the array into halves anyway, it is most natural to adapt it into a Merge-sort. Another point in favor of Merge-sort is that the searching process above can be embedded seamlessly into its merging stage.

So here is the Merge-sort-based solution, where the function “reversePairsSub” will return the total number of important reverse pairs within subarray nums[l, r]. The two-pointer searching process is represented by the nested while loop involving variable p, while the rest is the standard merging algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int reversePairs(int[] nums) {
return reversePairsSub(nums, 0, nums.length - 1);
}

private int reversePairsSub(int[] nums, int l, int r) {
if (l >= r) return 0;

int m = l + ((r - l) >> 1);
int res = reversePairsSub(nums, l, m) + reversePairsSub(nums, m + 1, r);

int i = l, j = m + 1, k = 0, p = m + 1;
int[] merge = new int[r - l + 1];

while (i <= m) {
while (p <= r && nums[i] > 2L * nums[p]) p++;
res += p - (m + 1);

while (j <= r && nums[i] >= nums[j]) merge[k++] = nums[j++];
merge[k++] = nums[i++];
}

while (j <= r) merge[k++] = nums[j++];

System.arraycopy(merge, 0, nums, l, merge.length);

return res;
}

III – Summary

Many problems involving arrays can be solved by breaking down the problem into subproblems applied on subarrays and then link the solution to the original problem with those of the subproblems, to which we have sequential recurrence relation and partition recurrence relation. For either case, it’s crucial to identify the subproblem C and find efficient algorithm for approaching it.

If the subproblem C involves searching on “dynamic searching space”, try to consider data structures that support relatively fast operations on both searching and updating (such as self-balanced BST, BIT, Segment tree, …).

If the subproblem C of partition recurrence relation involves sorting, Merge-sort would be a nice sorting algorithm to use. Also, the code could be made more elegant if the solution to the subproblem can be embedded into the merging process.

If there are overlapping among the subproblems T(i, j), it’s preferable to save the intermediate results for future lookup.

Last let me name a few leetcode problems that fall into the patterns described above and thus can be solved with similar ideas.

315. Count of Smaller Numbers After Self
327. Count of Range Sum

For leetcode 315, applying the sequential recurrence relation (with j fixed), the subproblem C reads: find the number of elements out of visited ones that are smaller than current element, which involves searching on “dynamic searching space”; applying the partition recurrence relation, we have a subproblem C: for each element in the left half, find the number of elements in the right half that are smaller than it, which can be embedded into the merging process by noting that these elements are exactly those swapped to its left during the merging process.

For leetcode 327, applying the sequential recurrence relation (with j fixed) on the pre-sum array, the subproblem C reads: find the number of elements out of visited ones that are within the given range, which again involves searching on “dynamic searching space”; applying the partition recurrence relation, we have a subproblem C: for each element in the left half, find the number of elements in the right half that are within the given range, which can be embedded into the merging process using the two-pointer technique.

Anyway, hope these ideas can sharpen your skills for solving array-related problems.


https://discuss.leetcode.com/topic/78950/java-merge-sort-solution-o-nlog-n

Java merge sort solution, O(nlog(n))

Similar with count smaller after self, just scan the array before merge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {

public int ret;
public int reversePairs(int[] nums) {
ret = 0;
mergeSort(nums, 0, nums.length-1);
return ret;
}

public void mergeSort(int[] nums, int left, int right) {
if (right <= left) {
return;
}
int middle = left + (right - left)/2;
mergeSort(nums, left, middle);
mergeSort(nums,middle+1, right);

//count elements
int count = 0;
for (int l = left, r = middle+1; l <= middle;) {
if (r > right || (long)nums[l] <= 2*(long)nums[r]) {
l++;
ret += count;
} else {
r++;
count++;
}
}

//merge sort
int[] temp = new int[right - left + 1];
for (int l = left, r = middle+1, k = 0; l <= middle || r <= right;) {
if (l <= middle && ((r > right) || nums[l] < nums[r])) {
temp[k++] = nums[l++];
} else {
temp[k++] = nums[r++];
}
}
for (int i = 0; i < temp.length; i++) {
nums[left + i] = temp[i];
}
}
}

Clearer and simpler version, but slower, got the idea by another solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {

public int ret;
public int reversePairs(int[] nums) {
ret = 0;
mergeSort(nums, 0, nums.length-1);
return ret;
}

public void mergeSort(int[] nums, int left, int right) {
if (right <= left) {
return;
}
int middle = left + (right - left)/2;
mergeSort(nums, left, middle);
mergeSort(nums,middle+1, right);

//count elements
int count = 0;
for (int l = left, r = middle+1; l <= middle;) {
if (r > right || (long)nums[l] <= 2*(long)nums[r]) {
l++;
ret += count;
} else {
r++;
count++;
}
}

//sort
Arrays.sort(nums, left, right + 1);
}
}

https://discuss.leetcode.com/topic/78943/clean-java-solution-using-enhanced-binary-search-tree

Clean Java Solution using Enhanced Binary Search Tree

This is literally the same problem with 315. Count of Smaller Numbers After Self.
The only difference is to find count of numbers smaller than half of the current number after itself.
To efficiently search for count of numbers smaller than a target, we can use a Binary Search Tree. There is a little change of the TreeNode to include count of numbers smaller or equal to it. This will make the query even faster because we don’t need to traverse all its left sub-tree to get the count.

Overall Algorithm:

  1. Scan the numbers from right to left.
  2. First search the tree to get count of numbers smaller than nums[i] / 2.0, sum to the final result.
  3. Insert nums[i] to the tree.

Insert logic:

  1. Recursively try to find a place to insert this number. When root is null, its time to create a new node. If meet the same number, just increase the count.
  2. When try to insert the number to left sub-tree, increase count of current node.

Query logic:

  1. If target value is greater than the current value, meaning current node and all left sub-tree are smaller than target, return count (remember it stands for count of numbers smaller or equal to current number) of current node plus any possible smaller number than target in right sub-tree.
  2. Otherwise, only search left sub-tree.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class Solution {
class Node {
int value, count;
Node left, right;
Node (int v) {
value = v; count = 1;
}
}

public int reversePairs(int[] nums) {
int result = 0;
if (nums == null || nums.length <= 1) return result;

int len = nums.length;
Node root = new Node(nums[len - 1]);

for(int i = len - 2; i >= 0; i--) {
result += query(root, nums[i] / 2.0);
insert(root, nums[i]);
}

return result;
}

private Node insert(Node root, int value) {
if (root == null) return new Node(value);

if (root.value == value) {
root.count++;
}
else if (root.value > value) {
root.count++;
root.left = insert(root.left, value);
}
else {
root.right = insert(root.right, value);
}

return root;
}

private int query(Node root, double value) {
if (root == null) return 0;

if (value > root.value) {
return root.count + query(root.right, value);
}
else {
return query(root.left, value);
}
}
}
谢谢你,可爱的朋友。