K Inverse Pairs Array
Hard · Dynamic Programming · Dynamic Programming · Prefix Sum
Problem
In an array nums, an inverse pair is a pair of indices (i, j) with i nums[j]: a larger number standing before a smaller one.
Given n and k, return how many orderings of the numbers 1 to n have exactly k inverse pairs. The count can be huge, so return it modulo 10^9 + 7.
Examples
Input: n = 3, k = 1 Output: 2
[1,3,2] and [2,1,3] each have one larger number before a smaller one.
Input: n = 4, k = 2 Output: 5
[1,3,4,2], [1,4,2,3], [2,1,4,3], [2,3,1,4] and [3,1,2,4].
Input: n = 3, k = 4 Output: 0
Three numbers have at most 3 inverse pairs, reached only by [3,2,1].
Constraints
- 1 <= n <= 1000
- 0 <= k <= 1000
Approaches
- DP over insertions, summing each window — time O(n · k · min(n, k)), space O(k)
Follow-up
The counts in one row are symmetric: an ordering with j inverse pairs reversed has n(n-1)/2 − j. So you never need k beyond half the maximum. Can you also answer “at most k inverse pairs”? Sum the final row up to k.
Related problems
Start free on Cariara · Coding problems · System design studio
