Reverse pairs


  • 0
    A

    Click here to see the full article post


  • 0
    T

    why cant we do it in linear time by keeping track of the minimum number ( comparing each number to the minimum ) and memoizing the result up till the previous value?


  • 0
    A

    @Tanvi09 the linear memoization would not give the correct answer. Let us take an example to understand: Let the array be A: 8 6 2 1 4 3 2. Here, the minimum numbers upto the current index are stored in min: 8 6 2 1 1 1 1. We will now move linearly over the array: ans=0 for 8. ans=0 for 6. ans=2(we add 2 since min[1]>2A[2] ). Now, for 1, (min[2] is not greater than 2A[2]), so, we cannot increment the ans. But, we see that {8,1} and {6,1} should have be counted. If we need to account for them, we need to check for min[1]. Since, we require to move back the array, the approach becomes O(n^2).


  • 0
    J

    In java, the BST used in this post will TLE. Because it can't avoid the worst case, and time complexity will be O(n) instead of O(logn). We can enhance it by sort the nums and construct the BST first. The BST is constructed by the sorted array, so we avoided the worst case. Note the node's count_ge field is zero. It will cumulate values that are larger in update stage.


  • 0

    @abhinavbansal0 this paragraph explaining the BST algorithm may need a rewrite.

    Each time, the given valval is smaller than Node.valNode.val, we increment the count_gecount_ge and move the valval to the right subtree. While, if the valval is equal to the current NodeNode, we simply increment the count_gecount_ge and exit. While, we move to the left subtree in case (\text{val}<\text{Node.val})(val<Node.val).


  • 0

    The following sentence is very confusing. in conventional BIT, such as in RangeSum problem, BIT[i] give the range sum [i - 2^r, i], r is the position of the last bit. Is the BIT you mentioned is different from the conventional one?

    According to the convention, query routine goes from index to 0, i.e., BIT[i] gives the sum for the range [0,index],


  • 0
    G

    @jack76 how does sort can avoid worst case?


Log in to reply
 

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