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)
1using System;
2class KInversePairs {
3 public int kInversePairs(int n, int k) {
4 int MOD = 1000000007;
5 int[,] dp = new int[n + 1, k + 1];
6 for (int i = 0; i <= n; i++) {
7 dp[i, 0] = 1;
8 for (int j = 1; j <= k; j++) {
9 if (i > 0) {
10 dp[i, j] = (dp[i-1, j] + MOD - (j >= i ? dp[i-1, j-i] : 0)) % MOD;
11 }
12 dp[i, j] = (dp[i, j] + dp[i, j-1]) % MOD;
13 }
14 }
15 return (dp[n, k] + MOD - (k > 0 ? dp[n, k-1] : 0)) % MOD;
16 }
17 static void Main() {
18 int n = 3, k = 1;
19 KInversePairs kip = new KInversePairs();
20 Console.WriteLine(kip.kInversePairs(n, k));
21 }
22}The C# solution creates a 2D array for DP and iterates through the array while using the same recursive logic as the previous solutions. The modulo operation is crucial for managing large integer values as required by the problem's constraints.
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.