## 629. K Inverse Pairs Array

Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.

We define an inverse pair as following: For ith and jth element in the array, if i < j and a[i] > a[j] then it's an inverse pair; Otherwise, it's not.

Since the answer may be very large, the answer should be modulo 109 + 7.

Example 1:

Input: n = 3, k = 0
Output: 1
Explanation:
Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pair.


Example 2:

Input: n = 3, k = 1
Output: 2
Explanation:
The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.


Note:

1. The integer n is in the range [1, 1000] and k is in the range [0, 1000].

b'
\n\n

## Solution

\n

#### Approach #1 Brute Force [Time Limit Exceeded]

\n

The most naive solution is to generate every permutation of the array consisting of numbers from to . Then, we can find out the number of inverse pairs in every array to determine if it is equal to 1. We can find out the count of permutations with the required number of inverse pairs. But, this solution is very terrible in terms of time complexity. Thus, we move on to the better approaches directly.

\n

Complexity Analysis

\n
\n
• \n

Time complexity : . A total of permutations will be generated. We need time to find the number of inverse pairs in every such permutation, by making use of merge sort. Here, refers to the given integer .

\n
• \n
• \n

Space complexity : . Each array generated during the permutations will require space.

\n
• \n
\n
\n

#### Approach #2 Using Recursion with memoization [Time Limit Exceeded]

\n

Before we discuss the solution, let\'s look at the idea behind it. Let\'s say, represents the given number defining the upper limit of the elements in the arrays being considered and represents the number of inverse pairs in the current array.

\n

Let\'s start with a simple example with , no is defined right now. Now, for , the only possible arrangement for the given array will be [1,2,3,4], since all the greater elements lie after the smaller elements. Now, in order to generate an arrangement with any arbitrary value, we need to shift, an arbitrary number of elements(let\'s say elements) in the array towards the left, with each displacement(shift) being , such that the sum of these shifts equals .

\n

To see what we mean by the above statement, let\'s look at the case for [1,2,4,3]. The number of inverse pairs in this array is 1. This array is obtained by shifting the number 4 by one position towards the left.

\n

Similarly, consider the case for [2,4,1,3]. This array can be obtained from by shifting 2 by one position towards the left first and then shifting 4 by 2 positions towards the left. Thus, the total number of displacements is 3, which is equal to the number of inverse pairs in the new array.

\n

This rule of displacements holds true because, whenever a number is shifted times towards the left starting from the array , after the shift, numbers smaller than it lie towards its right, giving a total of inverse pairs.

\n

Now, let\'s say, we start with the one of the arrangements \n[2,4,1,3], with . Now, if we want to add a new number 5 to this array to consider an array with , let\'s say, initially, we append it to the end of . Now, the new array will be [2,4,1,3,5]. Since, the largest number is added at the end, the new number 5 doesn\'t add any new inverse pair to the total set of inverse pairs relative to the ones in (3).

\n

Now, all the numbers in are smaller than 5. Thus, if we add 5 at a position steps from the right, smaller numbers will lie towards its right. Thus, a total of inverse pairs will exist with 5 being one of the elements in these pairs.

\n

Thus, adding 5 at steps from the right adds a total of inverse pairs to the total set of inverse pairs in giving a total of inverse pairs now.

\n

Looking at the same statement from another point of view, we can say that, if we know the number of inverse pairs(say ) in any arbitrary array with some , we can add a new element to this array at a position steps from the right, such that to generate an array with a total of inverse pairs.

\n

Extending this idea further, suppose we know the number of arrangements of an array with elements, with the number of inverse pairs being , let\'s say being equal to . Now, we can determine the number of arrangements of an array with elements with exactly inverse pairs easily.

\n

To generate the arrangements with exactly inverse pairs and elements, we can add the new number to all the arrangements with inverse pairs at the last position. For the arrangements with inverse pairs , we can add at a position 1 step from the right.

\n

Similarly, for an element with number of inverse pairs, we can add this new number at a position steps from the right. Each of these updations to the arrays leads to a new arrangement, each with the number of inverse pairs being equal to .

\n

The following image shows an example of how this is done for n=5 and k=4:

\n \n

Thus, to obtain the number of arrangements with exactly inverse pairs and numbers will be given by .

\n

From the above discussion, we can obtain the recursive formula for finding the number of arrangements with exactly inverse pairs as follows. Let\'s say represents the number of arrangements with elements and exactly inverse pairs.

\n
\n
1. \n

If , no inverse pairs exist. Thus, .

\n
2. \n
3. \n

If , only one arrangement is possible, which is all numbers sorted in ascending order. Thus, .

\n
4. \n
5. \n

Otherwise, .

\n
6. \n
\n

Note that the upper limit on the summation is . This is because for , . No arrangement exists with negative number of inverse pairs. The reason for the other factor can be seen as follows.

\n

To generate a new arrangement adding new inverse pairs after adding the number, we need to add this number at the position from the right. For an array with size , only maximum shifts are possible.

\n

We need to take the modulus at every step to keep the answer within integral limits.

\n

We can see that a lot of duplicate function calls are made in the normal recursive solution. We can remove this redundancy by making use of a memoization array which stores the result for any function call kInversePairs(i,j) in . Thus, whenver a duplicate function call is made again, we can return the result directly from this memoization array. This prunes the search space to a great extent.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . The function kInversePairs is called times to fill the array of size x. Each function call itself takes time.

\n
• \n
• \n

Space complexity : . array of constant size x is used. The depth of recursion tree can go upto .

\n
• \n
\n
\n

#### Approach #3 Dynamic Programming [Time Limit Exceeded]

\n

Algorithm

\n

As we\'ve seen in the discussion above, the solution for if we know the solutions for , ..., , we can directly obtain the solution for as .

\n

From this, we deduce that we can make use of Dynamic Programming to solve the given problem. To solve the given problem, we make use of a 2-D , where is used to store the number of arrangements with elements and exactly inverse pairs. Based on the discussions above, the updation equations become:

\n
\n
1. \n

If , no inverse pairs exist. Thus, .

\n
2. \n
3. \n

If , only one arrangement is possible, which is all numbers sorted in ascending order. Thus, .

\n
4. \n
5. \n

Otherwise, .

\n
6. \n
\n

Again, the limit is used to account for the cases where the number of inverse pairs needed becomes negative() or the case where the new inverse pairs needed by adding the number is more than which isn\'t possible, since the new number can be added at position at most from the right.

\n

We start filling the in a row-wise order starting from the first row. At the end, the value of gives the required result.

\n

The following animation shows how the is filled for n=4 and k=5:

\n

!?!../Documents/629_dp4.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . of size x is filled once. Filling each entry takes time.

\n
• \n
• \n

Space complexity : . array of size x is used.

\n
• \n
\n
\n

#### Approach #4 Dynamic Programming with Cumulative Sum[Accepted]:

\n

Algorithm

\n

From the last approach, we\'ve observed that we need to traverse back to some limit in the previous row of the array to fill in the current entry. Instead of doing this traversal to find the sum of the required elements, we can ease the process if we fill the cumulative sum upto the current element in a row in any entry, instead of the actual value.

\n

Thus, now, . Here, refers to the number of arrangements with elements and exactly inverse pairs. Thus, each entry contains the sum of all the previous elements in the same row along with its own result.

\n

Now, we need to determine the value of to be added to the sum of previous elements in a row, in order to update the entry. But, we need not traverse back in the previous row , since it contains entries representing the cumulative sums now.\nThus, to obtain the sum of elements from to (including both), we can directly use .

\n

Now, to reflect the condition used in the previous approaches, we can note that, we need to take the sum of only elements in the previous row, if elements exist till we reach the end of the array while traversing backwards. Otherwise, we simply take the sum of all the elements.

\n

Only elements are considered because for generating new inverse pairs, by adding as the new number at the position, could reach only upto , as discussed in the last approaches as well. Thus, we need to consider the sum of elements from to (including both) using if .

\n

Otherwise, we add all the elements of the previous row upto the current column being considered. In other words, we can use directly as the required sum.

\n

At the end, while returning the result, we need to return to obtain the required result from the cumulative sums.

\n

The following animation illustrates the process of filling the array.

\n

!?!../Documents/629_dp5.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . array of size x is filled once.

\n
• \n
• \n

Space complexity : . array of size x is used.

\n
• \n
\n
\n

#### Approach #5 Another Optimized Dynamic Programming Approach[Accepted]:

\n

Algorithm

\n

Another way to use the Dynamic Programming Approach could be if we can somehow directly store the required in entry, but still we should not need to traverse back in the previous row to find the sum of the required elements.

\n

To do so, we can note that for the row, we need to add the elements from to (including both) if . Otherwise, we need to add all the elements from to . This has already been discussed previously.

\n

Now, when we go for filling in after filling , we know already corresponds to the sum of the elements from to . But, for filling , we require the sum of the elements from to .

\n

We can observe that this sum only excludes from the previous sum() and requires addition of only one new element() to the to this sum. If the value , we need not remove any value.

\n

Thus, we can directly obtain value as , if . Otherwise, we can use: .

\n

We can also note that, since, here represents the number of inverse pairs that need to be currently considered, we can place another upper limit on as well. The maximum number of inverse pairs for any arbitrary occur only when the array is sorted in descending order leading to [n,n-1,....,3,2,1] as the arrangement.

\n

This arrangement has a total of inverse pairs. Thus, for an array with as the number of elements, the maximum number of inverse pairs possible is only. Thus, for fillling in the row of , we can place this limit on \'s value.

\n

The following animation shows the filling process.

\n

!?!../Documents/629_dp6.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . array of size x is filled once.

\n
• \n
• \n

Space complexity : . array of size x is used.

\n
• \n
\n
\n

#### Approach #6 Once Again Memoization [Accepted]:

\n

Algorithm

\n

The Dynamic Programming solution discussed in Approach 5 can also be written down in the form of a recursive solution. But, again, that will include a lot of duplicate function calls. Thus, a better solution would be to use memoization to store the results of the previous function calls.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . x entries in the array are filled once.

\n
• \n
• \n

Space complexity : . array of constant size x is used.

\n
• \n
\n
\n

#### Approach #7 1-D dynamic Programmming [Accepted]:

\n

Algorithm

\n

From the Dynamic Programming solution, we can also note that we only need the values of the previous row in the array, and not any other row. Thus, instead of storing the whole 2-D in memory, we can make use of a 1-D to store the previous row\'s entries only. The updations can be done in a 1-D array of the same size as and can be updated using this everytime a row is finished.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . array of size is filled times.

\n
• \n
• \n

Space complexity : . array of size is used.

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'