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).


Log in to reply
 

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