Scale Engineer

K Inverse Pairs Array

Hard
#0583Time: 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.1 company
Patterns
Dynamic Programming
Companies
Works Applications

Prompt

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 <= 1000
  • 0 <= 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_permutation has n elements.
  • In the base case, count the inverse pairs in the current_permutation. An inverse pair (i, j) exists if i < j and permutation[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 the current_permutation and 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_permutation has n elements.
  • In the base case, count the inverse pairs in the current_permutation. An inverse pair (i, j) exists if i < j and permutation[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 the current_permutation and 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

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.

← Previous

Previous problem

Next →

Next problem