For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].
Given two integers n and k, return the number of different arrays consisting of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it 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 pairs.
Example 2:
Input: n = 3, k = 1 Output: 2 Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.
Constraints:
1 <= n <= 10000 <= k <= 1000The key idea for #629 K Inverse Pairs Array is to count how many permutations of numbers 1..n contain exactly k inverse pairs. A brute-force approach of generating permutations is infeasible, so the problem is solved using dynamic programming.
Define dp[i][j] as the number of arrays using the first i numbers that contain exactly j inverse pairs. When inserting the number i into previous permutations, it can contribute between 0 and i-1 new inverse pairs depending on its position. This leads to the recurrence dp[i][j] = sum(dp[i-1][j-x]) for valid values of x.
To avoid recalculating repeated sums, use prefix sums to optimize the transition, reducing the complexity significantly. With this optimization, the algorithm runs in O(n × k) time and uses O(n × k) (or optimized O(k)) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Prefix Sum Optimization | O(n × k) | O(n × k) or O(k) with rolling array |
NeetCodeIO
We use a two-dimensional dynamic programming array, where dp[i][j] represents the number of permutations of array {1, 2, ..., i} with exactly j inverse pairs. The transition is based on the idea that when we insert a new element into an existing permutation, it can create new inverse pairs from 0 up to i-1.
Time Complexity: O(n*k)
Space Complexity: O(n*k)
1function kInversePairs(n, k) {
2 const MOD = 1000000007;
3 const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
4 for (let i = 0; i <= n; i++) {
5 dp[i][0] = 1;
6 for (let j = 1; j <= k; j++) {
7 if (i > 0) {
8 dp[i][j] = (dp[i-1][j] + MOD - (j >= i ? dp[i-1][j-i] : 0)) % MOD;
9 }
10 dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
11 }
12 }
13 return (dp[n][k] + MOD - (k > 0 ? dp[n][k-1] : 0)) % MOD;
14}
15
16const n = 3, k = 1;
17console.log(kInversePairs(n, k));In JavaScript, arrays are dynamically used to form the DP table. The algorithm applies the formula iteratively to populate results for inverse pair counts, ensuring efficient memory use and adhering to operation constraints with modulo handling.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of counting permutations with constraints and dynamic programming optimization problems are common in FAANG interviews. This problem tests understanding of DP states, transitions, and performance optimization.
The optimal approach uses dynamic programming where dp[i][j] represents the number of arrays using numbers 1..i with exactly j inverse pairs. Prefix sum optimization is applied to compute transitions efficiently and avoid repeated summations.
Dynamic programming works well because the number of inverse pairs for size i depends on previously computed results for size i-1. By storing intermediate states, we can build solutions incrementally and avoid recomputation.
A 2D DP array is typically used to store counts of permutations with specific inverse pair values. For optimization, prefix sums and rolling arrays can reduce the space usage while maintaining efficient transitions.