Watch 10 video solutions for K Inverse Pairs Array, a hard level problem involving Dynamic Programming. This walkthrough by NeetCodeIO has 18,853 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |