Start learning free

LESSON 317 OF 348 · DYNAMIC PROGRAMMING

Valley Permutations in Kotlin: Counting with Dynamic Programming

Practice O(n) Read the full explanation

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

A valley permutation is defined as a permutation that is a concatenation of two parts: a monotonically decreasing sequence and then a monotonically increasing sequence

Example:

Input: N = 4
Output: 8
Explanation: [
    [1, 2, 3, 4],
    [2, 1, 3, 4],
    [3, 1, 2, 4],
    [3, 2, 1, 4],
    [4, 1, 2, 3],
    [4, 2, 1, 3],
    [4, 3, 1, 2],
    [4, 3, 2, 1]
]
Notes: N <= 12
STEP 1 OF 6
    Ctrl + Enter to check

    KOTLIN · DYNAMIC PROGRAMMING

    Valley Permutations in Kotlin, explained

    Problem overview

    The function countPermutations receives a non-negative Int named n and returns how many valley permutations of length n exist. A permutation here is an arrangement of the numbers 1 to n, each used once. It is a valley permutation if it splits into two parts: a decreasing sequence, then an increasing sequence. Either part can be empty or have a single element, so a fully increasing or a fully decreasing arrangement also counts. The statement keeps n at 12 or below.

    For n = 4 the eight valley permutations are [1, 2, 3, 4], [2, 1, 3, 4], [3, 1, 2, 4], [3, 2, 1, 4], [4, 1, 2, 3], [4, 2, 1, 3], [4, 3, 1, 2] and [4, 3, 2, 1], so the answer is 8. Only the count is needed.

    Approach: place the largest number at an end

    Out of all n! permutations, only a few are valleys, so generating and testing each one would be slow. Counting is better.

    Look at where the largest number, i, can stand in a valley permutation of length i. The sequence falls to its lowest point and then rises. Every number strictly inside the sequence has a larger neighbour on at least one side: on the falling part the one before it is larger, on the rising part the one after it is, and at the bottom both are. The largest number has no larger neighbour, so it can't sit in the middle. It must be at the very first or the very last position.

    Remove it and what is left is a valley permutation of length i - 1. In the other direction, take any valley permutation of length i - 1 and put i at the front: the sequence still falls and then rises. Put it at the back instead: the same holds. The two results are different permutations. So each shorter valley permutation gives exactly two longer ones, which gives dp[i] = 2 * dp[i - 1] for i >= 2.

    Here is the step from length 2 to length 3. The valleys of length 2 are [1, 2] and [2, 1]. Putting 3 at the front gives [3, 1, 2] and [3, 2, 1]. Putting 3 at the back gives [1, 2, 3] and [2, 1, 3]. That is 4, and the two permutations left out, [1, 3, 2] and [2, 3, 1], have 3 in the middle, where it is a peak, not a valley.

    The base case is dp[1] = 1: a single number is one valley permutation. For length 1 the front and the back are the same position, which is why the doubling starts at i = 2.

    Step by step

    1. Handle n = 0 first. The empty permutation counts as a valley, because both parts are empty, so the answer is 1. The table below needs index 1, which doesn't exist when n is 0, so this case returns right away.
    2. Create dp as an IntArray of size n + 1, filled with zeros. dp[i] counts the valley permutations of length i.
    3. Set dp[1] = 1 as the base case.
    4. Loop i over 2..n, in increasing order.
    5. Compute dp[i] = 2 * dp[i - 1]: two positions for the largest number, times the shorter valleys.
    6. Return dp[n].

    The solution in Kotlin

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

    The Kotlin details worth a closer look:

    • Early return. A function with a block body can return from the middle. The guard keeps the rest of the code from touching dp[1] on an array of size 1.
    • val and arrays. val dp can't be reassigned, but its elements can change.
    • Inclusive range. 2..n includes n. For n = 1 the range 2..1 is empty, and the function returns dp[1], which is 1.

    The values follow a pattern: dp[i] is 2 to the power i - 1 for i >= 1. A brute-force check of all permutations for lengths 1 to 6 gives 1, 2, 4, 8, 16 and 32, the same as the table.

    Complexity

    Time: O(n). The loop does one multiplication per step.

    Space: O(n). The table has n + 1 entries. Only the previous entry is used, so a single running value would take O(1).

    Edge cases and common mistakes

    • n = 0. Returns 1 through the guard.
    • n = 1. Returns 1. The only permutation is [1].
    • n = 2. Returns 2: both [1, 2] and [2, 1] are valleys.
    • Doubling from i = 1. With only one position available for the number 1, doubling would give 2 for a single element.
    • Forgetting the guard. Without it, n = 0 throws ArrayIndexOutOfBoundsException at dp[1].
    • Treating valleys as strictly mixed. Fully increasing and fully decreasing permutations count, as the example for n = 4 shows with [1, 2, 3, 4] and [4, 3, 2, 1].

    Testing

    • n = 0 gives 1.
    • n = 1 gives 1.
    • n = 4 gives 8.
    • n = 12 gives 2048.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free