K Inverse Pairs Array

Hard
1618.

K Inverse Pairs Array

K Inverse Pairs Array is a hard coding problem on dynamic programming and prefix sum, asked in Amazon and Google interviews.

An inverse pair of an array nums is a pair of indices (i, j) with 0 <= i < j < nums.length and nums[i] > nums[j].

Given n and k, count the arrangements (permutations) of the numbers 1 to n that contain exactly k inverse pairs. The count can be huge, so return it modulo 10^9 + 7.

Example 1

Input
n = 3, k = 0
Output
1
Explanation
Only [1,2,3] has no inverse pair.

Example 2

Input
n = 3, k = 1
Output
2
Explanation
[1,3,2] and [2,1,3].

Example 3

Input
n = 4, k = 2
Output
5
Explanation
[1,3,4,2], [1,4,2,3], [2,1,4,3], [2,3,1,4] and [3,1,2,4].

Constraints

  • 1 <= n <= 1000
  • 0 <= k <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kInversePairs = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

K Inverse Pairs Array — Solution in Python, Java & C++

K Inverse Pairs Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

K Inverse Pairs Array is a hard coding problem on dynamic programming and prefix sum, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Dynamic Programming, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An inverse pair of an array nums is a pair of indices (i, j) with 0 <= i < j < nums.length and nums[i] > nums[j].

Given n and k, count the arrangements (permutations) of the numbers 1 to n that contain exactly k inverse pairs. The count can be huge, so return it modulo 10^9 + 7.

Example 1

Input: n = 3, k = 0
Output: 1
Explanation: Only [1,2,3] has no inverse pair.

Example 2

Input: n = 3, k = 1
Output: 2
Explanation: [1,3,2] and [2,1,3].

Example 3

Input: n = 4, k = 2
Output: 5
Explanation: [1,3,4,2], [1,4,2,3], [2,1,4,3], [2,3,1,4] and [3,1,2,4].

Constraints

  • 1 <= n <= 1000
  • 0 <= k <= 1000

Hints for K Inverse Pairs Array

  1. Hint 1

    Build the permutation by inserting the numbers in increasing order. Where can n go, and how many new inverse pairs does each spot create?

  2. Hint 2

    Placing n with t numbers after it creates exactly t new pairs, for t = 0 … n - 1, and it never changes the pairs among the smaller numbers. So dp[n][k] = dp[n-1][k] + dp[n-1][k-1] + … + dp[n-1][k-n+1].

  3. Hint 3

    That sum is a sliding window over the previous row: keep a running total, add dp[n-1][k] and subtract dp[n-1][k-n], so each entry costs O(1). Mind the modulus when subtracting.

How to solve K Inverse Pairs Array

Removing the largest value from a permutation of 1..n leaves a permutation of 1..n-1, and the largest value contributes exactly as many inverse pairs as there are elements after it (0 to n - 1). So the counts for n are window sums of the counts for n - 1.

Approach

  1. Start from dp = [1, 0, 0, …] (one arrangement of zero numbers, with zero pairs).
  2. For i = 1 … n, build next[j] = dp[j] + dp[j-1] + … + dp[j-i+1] (indices below 0 ignored) as a running window sum: add dp[j], and once j >= i subtract dp[j - i].
  3. Reduce every value modulo 10^9 + 7, adding the modulus back after a subtraction.
  4. Return dp[k] after the last row.

Why it works

The map "permutation of 1..i ↦ (permutation of 1..i-1 with i removed, number of elements after i)" is a bijection onto pairs (permutation, t) with 0 <= t <= i - 1, and the inverse-pair count of the original is the smaller permutation's count plus t. Summing over t gives the window recurrence, and the running sum computes each window in constant time.

Complexity

  • Time — O(n * k)
  • Space — O(k)

Pitfalls

  • The plain recurrence with an inner loop over t is O(n * k * n) — too slow at n = k = 1000.
  • After (window - dp[j - i]) the value can go negative: add 10^9 + 7 before taking the remainder.
  • Values of k above n(n-1)/2 are impossible and correctly come out as 0.

Reference solution

Python

def kInversePairs(n: int, k: int) -> int:
    MOD = 10**9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        nxt = [0] * (k + 1)
        window = 0
        for j in range(k + 1):
            window += dp[j]
            if j >= i:
                window -= dp[j - i]
            window %= MOD
            nxt[j] = window
        dp = nxt
    return dp[k]

Java

public static int kInversePairs(int n, int k) {
    final long MOD = 1000000007L;
    long[] dp = new long[k + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        long[] next = new long[k + 1];
        long window = 0;
        for (int j = 0; j <= k; j++) {
            window = (window + dp[j]) % MOD;
            if (j >= i) window = (window - dp[j - i] + MOD) % MOD;
            next[j] = window;
        }
        dp = next;
    }
    return (int) dp[k];
}

C++

int kInversePairs(int n, int k) {
    const long long MOD = 1000000007LL;
    vector<long long> dp(k + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        vector<long long> next(k + 1, 0);
        long long window = 0;
        for (int j = 0; j <= k; j++) {
            window = (window + dp[j]) % MOD;
            if (j >= i) window = (window - dp[j - i] + MOD) % MOD;
            next[j] = window;
        }
        dp = next;
    }
    return (int) dp[k];
}

JavaScript

var kInversePairs = function(n, k) {
    var MOD = 1000000007;
    var dp = new Array(k + 1).fill(0);
    dp[0] = 1;
    for (var i = 1; i <= n; i++) {
        var next = new Array(k + 1).fill(0);
        var window = 0;
        for (var j = 0; j <= k; j++) {
            window = (window + dp[j]) % MOD;
            if (j >= i) window = (window - dp[j - i] + MOD) % MOD;
            next[j] = window;
        }
        dp = next;
    }
    return dp[k];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Prefix Sum