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 <= 1000Problem Overview: Given integers n and k, count how many permutations of numbers 1..n contain exactly k inverse pairs. An inverse pair exists when i < j but nums[i] > nums[j]. The result can be very large, so the answer is returned modulo 1e9 + 7.
Approach 1: Dynamic Programming (Naive Transition) (Time: O(n*k*n), Space: O(n*k))
Define dp[i][j] as the number of arrays formed using numbers 1..i that contain exactly j inverse pairs. When inserting the number i into a permutation of size i-1, placing it at different positions creates additional inverse pairs. If you place i at position p from the end, it contributes p new inverse pairs. The transition becomes dp[i][j] = sum(dp[i-1][j-x]) for all valid x where 0 ≤ x < i. This directly simulates every possible insertion position, but the nested summation makes the time complexity O(n*k*n), which is too slow for large inputs.
Approach 2: Dynamic Programming with Prefix Sum Optimization (Time: O(n*k), Space: O(n*k))
The key observation is that the recurrence above repeatedly sums overlapping ranges. Instead of recomputing each sum, maintain a prefix sum over the previous row. This converts the transition into a constant-time range query: dp[i][j] = prefix[j] - prefix[j-i] (when j ≥ i). While iterating through j, maintain cumulative sums to build the next row efficiently. This removes the inner loop and reduces complexity to O(n*k). The technique is a classic optimization in dynamic programming where range-sum transitions are replaced with prefix sums. Modular arithmetic ensures values stay within limits.
This DP effectively models how permutations grow as the largest element is inserted into smaller permutations. Instead of enumerating permutations, it counts configurations mathematically. The prefix-sum trick transforms a cubic-style transition into a linear one over k, which is necessary for constraints up to n = 1000.
Recommended for interviews: The optimized DP with prefix sums is the expected solution. Interviewers often accept the basic DP recurrence first because it shows you understand how inverse pairs change when inserting elements. The optimized O(n*k) version demonstrates stronger mastery of dynamic programming transitions and range-sum optimization techniques commonly used in combinatorics-style counting problems.
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.
This solution initializes a DP table and iteratively fills it up using the recursive formula derived for permutation inverses. The modulo operation ensures that the values remain within bounds and computationally manageable.
Time Complexity: O(n*k)
Space Complexity: O(n*k)
We define f[i][j] as the number of arrays of length i with j inverse pairs. Initially, f[0][0] = 1, and the rest f[i][j] = 0.
Next, we consider how to obtain f[i][j].
Assume the first i-1 numbers are already determined, and now we need to insert the number i. We discuss the cases of inserting i into each position:
i is inserted into the 1st position, the number of inverse pairs increases by i-1, so f[i][j] += f[i-1][j-(i-1)].i is inserted into the 2nd position, the number of inverse pairs increases by i-2, so f[i][j] += f[i-1][j-(i-2)].i is inserted into the (i-1)th position, the number of inverse pairs increases by 1, so f[i][j] += f[i-1][j-1].i is inserted into the ith position, the number of inverse pairs does not change, so f[i][j] += f[i-1][j].Therefore, f[i][j] = sum_{k=1}^{i} f[i-1][j-(i-k)].
We notice that the calculation of f[i][j] actually involves prefix sums, so we can use prefix sums to optimize the calculation process. Moreover, since f[i][j] only depends on f[i-1][j], we can use a one-dimensional array to optimize the space complexity.
The time complexity is O(n times k), and the space complexity is O(k). Here, n and k are the array length and the number of inverse pairs, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n*k) |
| Dynamic Programming + Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Naive Transition) | O(n*k*n) | O(n*k) | Useful for understanding how inserting the largest element affects inverse pairs |
| Dynamic Programming with Prefix Sum Optimization | O(n*k) | O(n*k) | Best general solution for large constraints and interview settings |
K Inverse Pairs Array - Leetcode 629 - Python • NeetCodeIO • 18,853 views views
Watch 9 more video solutions →Practice K Inverse Pairs Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor