Start learning free

LESSON 341 OF 414 · DYNAMIC PROGRAMMING

Valley Permutations in Scala: Counting with a DP Table

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

    SCALA · DYNAMIC PROGRAMMING

    Valley Permutations in Scala, explained

    Problem overview

    The method countPermutations receives an Int n and returns the number of valley permutations of length n. A permutation of length n uses each of the numbers 1 to n exactly once. It is a valley permutation if it is a decreasing run followed by an increasing run, so its values fall to a lowest point and then rise.

    For n = 4 the answer is 8: [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]. Either run may be empty or have a single element, so a fully increasing or fully decreasing permutation also counts. The statement guarantees n is at most 12.

    Among the 24 permutations of length 4, only these 8 have the valley shape. Checking each permutation would work for small n but gets slow quickly, so the lesson finds a rule that counts them directly.

    Approach: where can the largest number go?

    Look at the position of the largest number, i, in a valley permutation of length i. Inside the decreasing run, every element is smaller than the one before it, so a large element must come at the start. Inside the increasing run, every element is larger than the one before it, so a large element must come at the end. The largest number can therefore only be the first element or the last element.

    Removing it from either end leaves a valley permutation of length i - 1: the remaining elements still fall and then rise. In the other direction, take any valley permutation of length i - 1 and place the new largest number at the front or at the back. Both results are valley permutations of length i, and they are different permutations. So each shorter permutation gives exactly two longer ones, and every longer one arises this way:

    count(i) = 2 * count(i - 1)

    The base case is count(1) = 1, since the permutation [1] is the only one. That gives 1, 2, 4, 8, ... , which matches the 8 listed for n = 4. The table is a short way to record each step of that argument.

    Step by step

    1. Handle n = 0 first. If n is 0, return 1. The empty permutation is the only permutation of length 0, and it counts as a valley permutation because both of its runs are empty. The table below starts from dp(1), which exists only when n is at least 1, so this case is answered directly.
    2. Create the table. dp is an Array[Int] of length n + 1 filled with zeros using Array.fill(n + 1)(0). Entry i will hold the number of valley permutations of length i.
    3. Set the base case. dp(1) = 1, since one number forms exactly one permutation.
    4. Loop over the lengths. i <- 2 to n visits each length from 2 up to n, and to includes n.
    5. Apply the recurrence. dp(i) = 2 * dp(i - 1): the largest number goes first or last.
    6. Return dp(n).

    The solution in Scala

    class Solution {
    def countPermutations(n: Int): Int = {
        if (n == 0) {
            return 1
        }
        val dp = Array.fill(n + 1)(0)
        dp(1) = 1
        for (i <- 2 to n) {
            dp(i) = 2 * dp(i - 1)
        }
        return dp(n)
    }
}

    The Scala details worth a closer look:

    • Array.fill(n + 1)(0). It has two parameter lists. The first is the size and the second is the value to repeat, so the call builds an Array[Int] of n + 1 zeros. new Array[Int](n + 1) would give the same array.
    • The early return. A Scala method normally returns its last expression, but return is the simplest way to leave early. Without the guard, dp(1) = 1 would throw an ArrayIndexOutOfBoundsException for n = 0, because the array has only index 0.
    • val fixes the name, not the elements. dp is a val, but dp(i) = ... changes an element of the array it refers to.
    • Round brackets and ranges. Array elements are read as dp(i). In 2 to n, the end is included. When n is 1, the range 2 to 1 is empty and the loop does nothing.
    • Size of the answer. The result is 2 to the power n - 1, which for n = 12 is 2,048. That is far below the limit of an Int, which is about 2.1 billion.

    Complexity

    Time: O(n). The loop runs at most n - 1 times and each pass does one multiplication.

    Space: O(n). The table has n + 1 entries. Since each entry depends only on the previous one, a single variable would reduce the space to O(1).

    Edge cases and common mistakes

    • n = 0. The guard returns 1 for the empty permutation.
    • n = 1. The loop is skipped and dp(1) is 1.
    • n = 2. Both [1, 2] and [2, 1] are valleys, so the answer is 2.
    • n = 3. The answer is 4. Among the six permutations of 1, 2, 3, the ones that fail are [1, 3, 2] and [2, 3, 1], which rise and then fall, the opposite of a valley.
    • Confusing valleys with all permutations. Multiplying by i instead of by 2 counts every permutation, which gives 24 for n = 4 instead of 8.
    • Forgetting the end positions. Counting only one end, for example putting the largest number first, halves every answer.

    Testing

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