# C++ with iterators

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

``````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());
}
};
``````

• Love the brevity and inplace_merge. BTW, I think you meant to remove "1" from "Solution1".

• @votrubac Oh, right. Thanks. Just a remainder of testing more variations (that turned out less nice). Btw, the "mid" iterator caused me to look up the proper name. The `inplace_merge` documentation) calls it "middle". But then I wondered why it uses "first" and "last" instead of "begin" and "end". Made a StackOverflow question of this.

• Thanks Stefan. It's quite cool to combine with merge sort. :-)
Just came up an idea, for the count accumulation part, I would made the following optimisation:

``````...
int mid = (start+end)/2;
...
for (int j = mid+1; j <= end; ++j) {
long long pivot = 2 * nums[j];
std::vector<int>::iterator itBegin = nums.begin()+start;
std::vector<int>::iterator itEnd = nums.begin()+mid+1;
std::pair<std::vector<int>::iterator, std::vector<int>::iterator> range = std::equal_range(itBegin, itEnd, 2*nums[j]);   <<< the equal_range here would be more efficient since each of the two partitions are already in order
if (range.second != itEnd) {
count += std::distance(range.second, itEnd);
}
}
...
``````

• @silentspring Your code is hard to read, could you please format it?

• Thank you so much for your concise, clean and elegant code!
This is my favorite implementation of "count inversions" problem so far.

One trivial question.
Will the expression " *i > 2L * *j " implicitly convert (*i) to "long" as well?
Will it work if " 1L *i > 2 * *j " ?
Is there anyway to avoid conversion? I was thinking x/2+x%2 > y, where x = *i, and y = *j. But it does not work for negative numbers.
Maybe you have some smarter ways :D
Thanks.

• @StefanPochmann
Sorry I did not know how to quote my code in this pane.
Updated my code snippet. And also apologise for misspelling your name. :-)

• @silentspring That's not an optimisation. You made it slower. It's only O(m log m) while mine is O(m), where m is the size of the halves. Plus you have the overhead of calling functions.

Btw, what is `long long pivot = 2 * nums[j];` supposed to achieve? Protect against overflow? When you store it as `long long`, the overflow has already happened. Well it doesn't matter because, um... you're not using `pivot` anyway. And why use `equal_range` when you then only use its `upper_bound` part?

• @yren2 said in C++ with iterators:

Will the expression " *i > 2L * *j " implicitly convert (*i) to "long" as well?

I don't know. But I suspect it does. Doesn't matter, though.

Will it work if " 1L *i > 2 * *j " ?

No, doesn't even compile. If you add `*` in the left side it compiles, but it's pointless. My `2L * *j` goes to `long` before the multiplication, protecting against overflow. Your `2 * *j` doesn't.

Is there anyway to avoid conversion? I was thinking x/2+x%2 > y, where x = *i, and y = *j. But it does not work for negative numbers.

You were close! `(*i >> 1) + (*i & 1) > *j` works.

Seems to be slower than mine, though. I did a test magnifying the time impact:

``````    int add;
for (int k=0; k<100; k++) {
for (auto i = begin, j = mid; i != mid; ++i) {
while (j != end and *i > 2L * *j)
++j;
add += j - mid;
}
}
``````

Tested with three different expressions five times each, here are the acceptance times in ms:

`*i > 2L * *j` => 933 949 942 1178 936
`*i > long(*j) << 1` => 1082 993 992 979 1059
`(*i >> 1) + (*i & 1) > *j` => 1312 1332 1135 1129 1149

• Hi, stefan, I love your coding style so much.
I can always learn a lot from your posts!

• @StefanPochmann
The pivot is a rubbish code which should have been deleted.

Oh ... I got your idea. Your is O(n) which is the most optimised.
For my version: I also should have used the std::upper_bound to get the first element within the 1st half which is greater than 2*nums[j]. But yeah, it makes it slower than yours.
Thank you very much!

• Great concise solution.

For the counting part, it seems that we could have an early termination right after `while` loop if `j` has reached `end` before `i` reaches `mid`:

• `if (j == end) { count += (mid-i)*(end-mid); break; }`.

This helps for arrays whose first half values are much bigger than second half, e.g., `[1000@10, 1000@1]`.

• @yren2 *j * 2L automatically converts *j from int to long, same for *i > *j * 2L

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.