K Inverse Pairs Array

Problem Statement:

Inverse pair is an even pair of numbers [i,j], where the first element of the array is i < j < nums.length and nums[i] > nums[j] is true. If the input to the programs is two integers n and k, then return the number of the different arrays containing numbers from 1 to n, which exactly have k inverse pairs. The answer you will find is rather big, that is, you should get it modulo 10^9 + 7.

Example 1:

Input: n = 3, k = 0

Output: 1

Explanation:

n = 3, which means we have integers from 1 to 3.

k = 0, indicating we need to find arrays with exactly 0 inverse pairs.

Now, let's list down all the possible arrays of length 3 (because n = 3) that can be formed using numbers from 1 to 3:

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

Now, let's check how many inverse pairs each of these arrays has:

• [1, 2, 3] - 0 inverse pairs
• [1, 3, 2] - 1 inverse pair ([3, 2])
• [2, 1, 3] - 1 inverse pair ([2, 1])
• [2, 3, 1] - 1 inverse pair ([2, 1])
• [3, 1, 2] - 2 inverse pairs ([3, 1], [3, 2])
• [3, 2, 1] - 3 inverse pairs ([3, 2], [3, 1], [2, 1])

Only the first array ([1, 2, 3]) has exactly 0 inverse pairs, which is what we're looking for according to the given conditions. So, there's only one array that satisfies the requirement; hence, the output is 1.

Example 2:

Input: n = 3, k = 1

Output: 2

Explanation:

n = 3, meaning we have integers from 1 to 3.

k = 1, indicating we need to find arrays with exactly 1 inverse pair.

Now, let's list down all possible arrays of length 3 using numbers from 1 to 3:

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

Now, let's count the number of inverse pairs for each of these arrays:

• [1, 2, 3] - 0 inverse pairs
• [1, 3, 2] - 1 inverse pair ([3, 2])
• [2, 1, 3] - 1 inverse pair ([2, 1])
• [2, 3, 1] - 2 inverse pairs ([2, 1], [3, 1])
• [3, 1, 2] - 2 inverse pairs ([3, 1], [3, 2])
• [3, 2, 1] - 3 inverse pairs ([3, 2], [3, 1], [2, 1])

Out of these arrays, two arrays have exactly 1 inverse pair:

• [1, 3, 2]
• [2, 1, 3]

Therefore, the output is 2.

Java Approach Using Dynamic Programming:

Output:

Time Complexity:

• The asymptotic complexity of the kInversePairs method is O(n*k), which is the product of the length of the array 'n' and the number of inverse pairs 'k'.

Space Complexity:

• In addition to time complexity it has O(n*k) space complexity, too. The reason for this is that we have a 2D array 'dp' with the size of (n + 1) * (k + 1).

Java Approach Using Dynamic programming without Recursion

Output:

Time Complexity:

• The exponential time complexity is O (n* k), whereas, n is the input value and k the output value. This is due to the fact that there are iterations in the solution for n times which require operations for every value of 'k' individually, in the limit specified.

Space Complexity:

• The space complexity of the solutions amounts to О(k), where 'k' is the value of input argument 'k'. This is resulting from use of two arrays of size 'k + 1' for intermediate results while dynamic programming approach is applied. So, the size is growing linearly with the value of 'k'.

Java Approach Using Recursion

Output:

Time Complexity:

• The time complexity of a recursive solution is exponential because of the recursive function which is called a lot (more than once) each combination of n and k initialize. It is (n * k).

Space Complexity:

• Similarly with the space complexity we also have in O(n * k) where we store the memoization array used to store immediate results, too. The array has a size n * k with the meaning n=length of the array and k=number of inverse pairs formed.