LESSON 322 OF 348 · DYNAMIC PROGRAMMING

Permutations With K Inversions in TypeScript: Dynamic Programming

Practice O(n * k) Read the full explanation

Given two non-negative integers N and K, return the number permutations of length N with exactly K inversions

An inversion is a pair of indices (i, j) with i < j and p(i) > p(j)

Example:

Input: N = 4, K = 2
Output: 5
Explanation: [
    [1, 3, 4, 2],
    [1, 4, 2, 3],
    [1, 4, 3, 2],
    [2, 1, 4, 3],
    [3, 1, 2, 4],
]

Notes:
N <= 12
K <= N * (N - 1)) / 2

STEP 1 OF 7

Guided

Ctrl + Enter to check

TYPESCRIPT · DYNAMIC PROGRAMMING

Permutations With K Inversions in TypeScript, explained

Problem overview

The method countPermutations(n, k) returns how many permutations of length n have exactly k inversions. A permutation here uses each of the numbers 1 to n once. An inversion is a pair of positions i < j where the earlier value is larger: p[i] > p[j].

For n = 4 and k = 2 the answer is 5. The permutation [1, 3, 4, 2] has two inversions, because both 3 and 4 come before 2. The five permutations are [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 4, 3], [2, 3, 1, 4] and [3, 1, 2, 4]. For comparison, [1, 4, 3, 2] has three inversions (4 over 3, 4 over 2 and 3 over 2), so it doesn't belong to this count.

Approach: insert the largest element

Listing all permutations and counting their inversions takes n! steps. For n = 12 that is 479,001,600 permutations, too many to enumerate and check pair by pair.

The faster idea builds permutations one length at a time. Let dp[i][j] be the number of permutations of length i with exactly j inversions. To get a permutation of length i + 1, take one of length i and insert the new largest value, i + 1, somewhere. The new value is bigger than everything else, so it forms an inversion with every element that ends up to its right, and with none to its left.

Inserting it at the very end adds 0 inversions.
Inserting it one slot further left adds 1.
Inserting it at the very front adds i.

So a permutation of length i has i + 1 insertion slots, adding between 0 and i inversions, and each slot gives a different permutation. Every permutation of length i + 1 comes from exactly one smaller permutation (remove its largest value), so adding the counts never double counts.

Here is the table for k = 3:

length 1: [1, 0, 0, 0]
length 2: [1, 1, 0, 0]
length 3: [1, 2, 2, 1]

Length 3 is computed from length 2. The one permutation with 0 inversions spreads over 0, 1 and 2; the one with 1 inversion spreads over 1, 2 and 3. That gives 1, 2, 2, 1 for 0 to 3 inversions, which matches the six permutations of three elements.

Step by step

Build the table. Create n + 1 rows, each with k + 1 zeros. Row i is for length i, and column j for j inversions.
Seed length 1. The single permutation [1] has no inversions, so dp[1][0] = 1.
Loop over lengths i from 1 to n - 1. Each pass fills row i + 1, so the last pass fills row n.
Loop over inversion counts j from 0 to k, so every state with a nonzero count is extended.
Cap the range. Inserting adds 0 to i inversions, so the new counts run from j to j + i. Store Math.min(j + i, k) in hi, because counts above k can never lead back down to the answer.
Add the ways forward. For each j1 from j to hi, add dp[i][j] to dp[i + 1][j1].
Return dp[n][k].

The solution in TypeScript

class Solution {
    countPermutations(n: number, k: number): number {
        const dp: number[][] = [];
        for (let i = 0; i <= n; i++) {
            dp.push(new Array(k + 1).fill(0));
        }
        dp[1][0] = 1;
        for (let i = 1; i < n; i++) {
            for (let j = 0; j <= k; j++) {
                const hi = Math.min(j + i, k);
                for (let j1 = j; j1 <= hi; j1++) {
                    dp[i + 1][j1] += dp[i][j];
                }
            }
        }
        return dp[n][k];
    }
}

TypeScript details worth knowing:

const dp still allows changes. The binding is fixed, but push and cell assignments modify the array. const hi is declared inside the loop, so each pass gets a fresh binding.
Separate rows. The new Array(k + 1).fill(0) expression runs once per pass of the first loop, so the rows don't share storage. fill is what puts numbers in; without it the slots are empty and sums give NaN.
Numbers are doubles. There is no integer overflow to worry about. For n = 12 the largest possible count is 12!, far below 2^53, so everything stays exact.
Types vanish at run time. n: number checks your calls while you write them, but the compiled JavaScript doesn't check anything.
Indexing past the table. Reading dp[i][j] with a bad row index gives undefined for the row, and indexing that throws a TypeError. This is what happens in the next section for n = 0.

Complexity

Time: O(n * n * k). The outer loop runs n - 1 times, the middle one k + 1 times, and the inner one at most i + 1 times, which is at most n. For n = 12 this is tiny.

Space: O(n * k). The table has (n + 1) * (k + 1) cells. Row i + 1 depends only on row i, so two rows would be enough.

Edge cases and common mistakes

k = 0. Only the sorted permutation has no inversions, so the answer is 1. For n = 3 and k = 0 the function returns 1.
The maximum k. The reversed permutation has the most inversions, n * (n - 1) / 2, and it is unique. For n = 12 and k = 66 the answer is 1.
k beyond the maximum. For n = 4 and k = 7 the result is 0, because no permutation has that many inversions.
n = 1. The loop never runs and dp[1][0] is returned: 1 for k = 0.
n = 0. The table has only row 0, so dp[1][0] = 1 throws a TypeError. The lesson only asks for lengths of at least 1, but a guard such as returning early would be needed to support 0.
Forgetting the cap. Without Math.min(j + i, k), the inner loop would write to columns beyond k, stretching the rows with NaN values.
Starting the middle loop at 1. The 0 column holds the sorted permutations and must be extended too.

Testing

n = 4, k = 2 gives 5.
n = 3, k = 1 gives 2.
n = 4, k = 3 gives 6, the middle of the row 1, 3, 5, 6, 5, 3, 1 for n = 4.
n = 6, k = 7 gives 101.
n = 12, k = 66 gives 1.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free