493. Reverse Pairs

Most of the codes will either not pass the TLE or have very bad performance. There are majorly 2 types of algorithms in Leetcode (BST, merge sort), but neither should be considered as the standard solution. The idea of the algorithms are simply sort the sub list and count how many numbers match the condition. They are in O(nlog(n)) complexity.

But the code below is written by the contest champion and is in O(n) complexity.

I am not saying I understand this code 100%, but I will try to elaborate it as deep as possible.

Obviously "lowbit" means the lowest non-zero bit in a number.

"Add" which is adding all the "pattern" for identifying a number larger than or equal to x (x is the input)
"que" is just seeing, if x match one of the pattern added by "Add"

say, you have input [1,3,2,3,1]
(I will list it as 4 bit number for convenient)
for number 1, the pattern will be 0b0001, 0b0010, 0b0100, 0b1000. This is saying, if a number is none 0 in either of the 4 bits. It will be at least as large as 1. This is a sufficient and necessary condition.

For number 3, the pattern will be 0b0101, 0b0110, 0b1000. As long as you have a number, which has none 0 digits in either of the pattern, the number will be at least as large as 3.

The important point is, when you sequentially remove a number's lowest bit 1, the number will eventually, match only one patter in a number, not two patter. But it can match one pattern in 1 and one pattern in 3.

The patterns of the larger number are also sufficient for the the patterns of the smaller number. Such that any number larger than number 3 will match pattern 0b0101, 0b0110, 0b1000, and it will also match 0b0001, 0b0010, 0b0100, 0b1000. But not the other way around.

This makes the pattern stack able. When you stack the patterns for number 3 and number 1, you got

0b0101:1
0b0110:1
0b1000:2
0b0001:1
0b0010:1
0b0100:1

thus, when you have a number and we sequentially remove the lowest bit and trying to find the matching pattern, you got the counts of numbers lower than the input number.

Leave a Reply

Your email address will not be published. Required fields are marked *