LESSON 316 OF 348 · DYNAMIC PROGRAMMING

Permutations of Given Length in Kotlin: Counting with DP

Given a non-negative integer N return the number permutations of length N

Example:

Input: N = 3
Output: 6
Explanation: [
    [1, 2, 3],
    [1, 3, 2],
    [2, 1, 3],
    [2, 3, 1],
    [3, 1, 2],
    [3, 2, 1]
]

Notes: N <= 12

STEP 1 OF 5

Guided

Ctrl + Enter to check

KOTLIN · DYNAMIC PROGRAMMING

Permutations Of Given Length in Kotlin, explained

Problem overview

The function countPermutations receives a non-negative Int named n and returns the number of permutations of length n: the ways to arrange the numbers 1 to n in a row, using each exactly once. Only the count is needed. The statement keeps n at 12 or below.

For n = 3 the six permutations 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.

Approach: choose the first element, then arrange the rest

To build a permutation of length i, first choose which number goes in front. There are i choices. Whatever the choice, the remaining i - 1 numbers can be arranged in any of the ways that permutations of length i - 1 can, because only their relative order matters, not which numbers they are. So the count for length i is i times the count for length i - 1.

With dp[i] as the number of permutations of length i, that is dp[i] = i * dp[i - 1]. This is the factorial, i!. The base case is dp[0] = 1: there is exactly one way to arrange nothing, the empty permutation. Then dp[1] = 1 * dp[0] = 1, dp[2] = 2, dp[3] = 6, and so on.

Starting at length 0 instead of length 1 also answers n = 0 correctly, with no special case.

Step by step

Create dp as an IntArray of size n + 1, so index n exists. It starts with zeros.
Set dp[0] = 1, the empty permutation. Every longer length is built from it. For n = 0 the array has only index 0, which is exactly the one that was set.
Loop i over 1..n in increasing order, so dp[i - 1] is always ready when needed.
Set dp[i] = i * dp[i - 1]: i choices for the first element times the arrangements of the rest.
Return dp[n] below the loop.

The solution in Kotlin

class Solution {
    fun countPermutations(n: Int): Int {
        val dp = IntArray(n + 1)
        dp[0] = 1
        for (i in 1..n) {
            dp[i] = i * dp[i - 1]
        }
        return dp[n]
    }
}

The Kotlin details worth a closer look:

Inclusive range. 1..n includes n. When n is 0, the range is empty and the loop never runs.
Fixed-size array. IntArray(n + 1) has exactly n + 1 slots. Writing to a slot beyond that throws ArrayIndexOutOfBoundsException.
Silent overflow. Int holds values up to 2,147,483,647. 12! is 479,001,600, which fits, so the statement's limit of 12 is safe. 13! is 6,227,020,800, which doesn't: countPermutations(13) returns 1932053504, a wrong number with no error. Use Long if you need larger values, which works up to n = 20.

Complexity

Time: O(n). The loop runs n times with one multiplication each.

Space: O(n). The table has n + 1 entries. Since each entry depends only on the one before it, a single running product would use O(1) space. The table shows the recurrence and keeps all the smaller answers visible, which is the idea behind dynamic programming.

Edge cases and common mistakes

n = 0. The answer is 1, and the code returns dp[0], which is 1.
n = 1. The answer is 1.
Base case 0. If dp[0] were left at 0, every entry after it would be 0 too, since each one multiplies the previous.
Multiplying by i - 1. The first element has i choices, not i - 1. That mistake gives 0 at i = 1.
Exceeding 12. Past 12 the Int result wraps around without any error.
Mixing up with combinations. This counts ordered arrangements of all n numbers. Choosing a subset is a different count.

Testing

n = 0 gives 1.
n = 1 gives 1.
n = 3 gives 6.
n = 12 gives 479001600.

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

Start learning free