K Inverse Pairs Array
HardPrompt
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 <= 1000
Approaches
4 approaches with complexity analysis and trade-offs.
This approach involves generating every possible permutation of numbers from 1 to n. For each generated permutation, we count the number of inverse pairs. If the count matches k, we increment our result. This method is conceptually simple but computationally very expensive.
Algorithm
- Define a recursive function, say
generatePermutations(current_permutation, used_numbers). - The base case for the recursion is when the
current_permutationhasnelements. - In the base case, count the inverse pairs in the
current_permutation. An inverse pair(i, j)exists ifi < jandpermutation[i] > permutation[j]. - If the number of inverse pairs is exactly
k, increment a global counter. - In the recursive step, iterate through numbers from 1 to
n. If a number has not been used, add it to thecurrent_permutationand make a recursive call. - Backtrack by removing the number and marking it as unused to explore other possibilities.
Walkthrough
The brute-force method explores all possible arrangements of the numbers from 1 to n. It uses a backtracking algorithm to generate each permutation. Once a full permutation of n numbers is formed, it iterates through the permutation to count the number of inverse pairs. If this count equals the target k, a solution is found.
Algorithm:
- Define a recursive function, say
generate(current_permutation, used_numbers). - The base case for the recursion is when the
current_permutationhasnelements. - In the base case, count the inverse pairs in the
current_permutation. An inverse pair(i, j)exists ifi < jandpermutation[i] > permutation[j]. - If the number of inverse pairs is exactly
k, increment a counter. - In the recursive step, iterate through numbers from 1 to
n. If a number has not been used, add it to thecurrent_permutationand make a recursive call. - Backtrack by removing the number and marking it as unused to explore other possibilities.
// This is a conceptual implementation and is too slow to pass.class Solution { int count = 0; int N, K; public int kInversePairs(int n, int k) { this.N = n; this.K = k; // The maximum number of inversions for n elements is n*(n-1)/2. if (k > n * (n - 1) / 2) { return 0; } List<Integer> permutation = new ArrayList<>(); boolean[] used = new boolean[n + 1]; generate(permutation, used); return count; } private void generate(List<Integer> permutation, boolean[] used) { if (permutation.size() == N) { if (countInversions(permutation) == K) { count++; } return; } for (int i = 1; i <= N; i++) { if (!used[i]) { used[i] = true; permutation.add(i); generate(permutation, used); permutation.remove(permutation.size() - 1); used[i] = false; } } } private int countInversions(List<Integer> arr) { int inversions = 0; for (int i = 0; i < arr.size(); i++) { for (int j = i + 1; j < arr.size(); j++) { if (arr.get(i) > arr.get(j)) { inversions++; } } } return inversions; }}Complexity
Time
O(n! * n^2) - There are `n!` permutations. For each permutation, we spend `O(n^2)` to count the inversions.
Space
O(n) - For the recursion stack depth and to store the current permutation.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient and will time out for all but the smallest values of
n(e.g., n > 10).
Solutions
Solution
class Solution {public int kInversePairs(int n, int k) { final int mod = (int)1 e9 + 7; int[] f = new int[k + 1]; int[] s = new int[k + 2]; f[0] = 1; Arrays.fill(s, 1); s[0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= k; ++j) { f[j] = (s[j + 1] - s[Math.max(0, j - (i - 1))] + mod) % mod; } for (int j = 1; j <= k + 1; ++j) { s[j] = (s[j - 1] + f[j - 1]) % mod; } } return f[k]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.