Problem overview
The method countPermutations receives a non-negative integer n and returns how many permutations of length n exist, that is, how many ways the numbers 1 to n can be arranged in a row, each used exactly once. For n = 3 the six arrangements are [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] and [3, 2, 1], so the answer is 6. The statement limits n to 12.
Only the number of permutations is needed, not the permutations themselves.
Approach: choose the first element, then arrange the rest
To build a permutation of length i, first choose which of the i numbers goes in the first position. Once that is fixed, the remaining i - 1 numbers can be arranged in as many ways as there are permutations of length i - 1. The choices are independent, so the counts multiply:
dp[i] = i * dp[i - 1]
This is the factorial: dp[i] is i!. The base case is dp[0] = 1: there is exactly one way to arrange nothing, the empty permutation. With it, dp[1] comes out as 1 * 1 = 1 without a special case.
Two different choices of first element always give different permutations, and two arrangements of the rest give different permutations too, so nothing is counted twice and nothing is missed.
For n = 3 the table is 1, 1, 2, 6, and the answer is its last entry. Reading it off the example: the six permutations split into three groups of two by their first element (1, 2 or 3), and each group holds the two arrangements of the two numbers left over. That is 3 * 2 = 6.
Counting this way is what keeps the work small. Generating every permutation of 12 numbers would mean handling 479,001,600 lists, while the table needs 12 multiplications.
Step by step
- Declare
dpas anumber[]withn + 1elements. The extra slot makes indexnexist. - Set
dp[0]to 1. Starting at length 0 also makesn = 0work, where the table has just one index. - Loop with
ifrom 1 up to and includingn, sodp[i - 1]is always ready whendp[i]needs it. - Multiply:
dp[i]isi * dp[i - 1]. - Return
dp[n].
The solution in TypeScript
class Solution {
countPermutations(n: number): number {
let dp: number[] = new Array(n + 1);
dp[0] = 1;
for (let i = 1; i <= n; i++) {
dp[i] = i * dp[i - 1];
}
return dp[n];
}
}
TypeScript details worth knowing:
- Empty slots.
new Array(n + 1)has no values yet; reading a slot that was never written givesundefined. The loop always writesdp[i]after reading onlydp[i - 1], which is already set. - Numbers are doubles. There is no 32-bit overflow in TypeScript. The largest answer here,
12! = 479001600, would fit even in a 32-bit integer,, so the limit of 12 is far from any precision problem. - Type annotations are erased.
number[]is checked by the compiler and doesn't exist at run time.
Complexity
Time: O(n). One multiplication per loop pass.
Space: O(n). The table holds n + 1 numbers. Only the previous value is ever needed, so a single running product would use O(1).
Edge cases and common mistakes
n = 0. The loop doesn't run, and the function returnsdp[0], which is 1: the empty permutation.n = 1. The answer is 1.- Forgetting the base case. Without
dp[0] = 1, the first pass computes1 * undefined, which isNaN, and every later entry isNaNas well. - Starting the table at 0. Setting
dp[0] = 0makes every product 0. - Stopping at
i < n. The last entry would never be written and the function would returnundefinedfornof 1 or more. - Adding instead of multiplying. The choices are independent, so counts multiply: for each of the
ifirst elements there aredp[i - 1]arrangements of the rest.
Testing
n = 0gives1.n = 1gives1.n = 3gives6.n = 4gives24.n = 12gives479001600.