Start learning free

LESSON 308 OF 338 · DYNAMIC PROGRAMMING

Valley Permutations in Go: Counting with a Doubling DP

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

    GO · DYNAMIC PROGRAMMING

    Valley Permutations in Go, explained

    Problem overview

    The function countPermutations takes an int n and returns the number of valley permutations of length n. A permutation arranges the numbers 1 to n, each used once. It is a valley permutation if it is a decreasing run followed by an increasing run, so the values fall to a lowest point and then rise. Either run may be empty, so a fully increasing or fully decreasing arrangement counts too. The lesson's notes say n is at most 12.

    For n = 4 the answer is 8. The 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]. Out of the 24 permutations of four numbers, the other 16 go up and down more than once.

    Approach: place the largest number at an end

    In a valley, the smallest value is the bottom, and the values rise as you move away from it in either direction. Every value other than the bottom therefore has a larger neighbour on the side facing away from the bottom. The largest value, i, has no larger neighbour, so it can't be one of those positions. For i > 1 it is not the bottom either, so it must stand at the first or the last position, where there is no neighbour on one side.

    Remove i from either end. What remains is a valley permutation of length i - 1: the shape of the remaining numbers is unchanged. Going the other way, take any valley permutation of length i - 1 and put i in front of it or after it. Both results are valleys, and they are different permutations. So each valley permutation of length i - 1 yields exactly two of length i, and the count doubles each time.

    The base case is dp[1] = 1. A single number is its own valley. The length 0 is handled separately, since the table starts at 1.

    Step by step

    1. Handle n == 0 first: return 1. The empty permutation is the only one of length 0, and it counts as a valley, since both of its parts are empty. The table below needs index 1, which does not exist for n = 0.
    2. Create the table with make([]int, n+1). It is filled with zeros, and dp[i] will hold the count for length i.
    3. Set dp[1] = 1.
    4. Loop with i from 2 up to and including n.
    5. Double: dp[i] = 2 * dp[i-1].
    6. Return dp[n].

    The solution in Go

    func countPermutations(n int) int {
    if n == 0 {
        return 1
    }
    dp := make([]int, n+1)
    dp[1] = 1
    for i := 2; i <= n; i++ {
        dp[i] = 2 * dp[i-1]
    }
    return dp[n]
}

    The Go details worth a closer look:

    • if without parentheses. The condition n == 0 needs no parentheses, and the braces are required even for a single statement.
    • The early return is not optional. Without it, dp[1] = 1 on a slice of length 1 panics at run time with an index out of range error. Go checks every slice index while the program runs.
    • make([]int, n+1). It creates a slice whose elements are all 0. A slice is the right choice for a size that is only known at run time.
    • Size. The answer is 2^(n-1), which for n = 12 is 2048, far inside the range of int.

    Complexity

    Time: O(n) for the loop. Space: O(n) for the table. Keeping a single variable instead of the table gives O(1) space, and the closed form 1 << (n - 1) is a shortcut for n >= 1.

    Edge cases and common mistakes

    • n = 0. Returns 1 through the early check.
    • n = 1. The loop does not run, and dp[1] is 1.
    • n = 2. Both [1, 2] and [2, 1] are valleys, and the function returns 2.
    • Expecting 2^n. The table starts at 1 for n = 1, so the result is 2^(n-1). Starting dp[1] at 2 would be wrong: for n = 1 there is only one arrangement.
    • Counting the largest value in the middle. A permutation such as [1, 3, 2] goes up and then down, which is the opposite shape, a peak. It is not a valley.
    • Using the factorial instead. For n = 4, 24 would be the count of all permutations, not those with the valley shape.

    Testing

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