Start learning free

LESSON 316 OF 347 · DYNAMIC PROGRAMMING

Valley Permutations in C#: 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

    C# · DYNAMIC PROGRAMMING

    Valley Permutations in C#, explained

    Problem overview

    The method CountPermutations receives an integer n and returns how many valley permutations of length n exist. A valley permutation of the numbers 1 to n is a decreasing run followed by an increasing run. For n = 4 there are 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
4 3 2 1

    The notes say n is at most 12. Either run can be empty, so a fully increasing or fully decreasing arrangement also counts.

    Approach: where does the largest number go?

    Look at the largest number, i, in a valley permutation of length i. The shape is "down, then up", so the largest value can't sit in the middle: it is bigger than both neighbours, and that would make a peak. It must be at one end, first or last.

    Remove it, and what is left is a valley permutation of length i - 1. Going the other way, each valley permutation of length i - 1 can take the new largest number at the front or at the back, and both results are valid valleys. The two placements give different permutations, so every shorter permutation produces exactly two longer ones:

    dp[i] = 2 * dp[i - 1]

    With dp[1] = 1, the table goes 1, 2, 4, 8, so n = 4 gives 8, matching the list above. For a single number the two placements coincide, which is why the doubling starts at length 2, not 1.

    Here is the argument on n = 3. The valley permutations of length 2 are 12 and 21. Put 3 at the front and you get 312 and 321. Put 3 at the back and you get 123 and 213. Those are the four valleys of length 3, and no other arrangement works: 132 and 231 would have 3 in the middle, with a smaller number on each side, so they go up and then down.

    It helps to see why removing the largest value keeps the shape. Taking a number off the end of a decreasing-then-increasing sequence leaves a sequence that is still decreasing-then-increasing, because a run that loses its first or last element is still a run (or becomes empty). The reverse direction, adding a larger number at either end, also keeps both runs valid: at the front it extends the decreasing run, and at the back it extends the increasing run.

    Why there is no double counting

    When i is at least 2, the largest number is either first or last, never both, so the permutations with it first and those with it last are different sets. Each set has exactly dp[i - 1] members, one for every valley permutation of the remaining numbers. Adding the two sets gives the doubling. For i = 1 the single element is both first and last, which is why the base case is 1 and not 2.

    Step by step

    1. Handle n = 0 first and return 1. The empty permutation counts as a valley (both runs are empty), and the table below needs index 1, which doesn't exist when n is 0.
    2. Create the table dp, an int[] of length n + 1, all zeros.
    3. Set dp[1] to 1: one number forms exactly one valley permutation.
    4. Loop from 2 to n inclusive.
    5. Double: dp[i] = 2 * dp[i - 1].
    6. Return dp[n].

    The solution in C#

    class Solution {

    public int CountPermutations(int n) {
        if (n == 0) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = 2 * dp[i - 1];
        }
        return dp[n];
    }
}

    C# details worth knowing:

    • The early return protects the array. For n = 0, new int[1] has only index 0, and dp[1] = 1 would throw IndexOutOfRangeException.
    • No overflow. The result is 2 to the power n - 1, which is 2048 for n = 12, far below the int limit.
    • The closed form. Since each step doubles, 1 << (n - 1) gives the same answer for n >= 1. The table keeps the reasoning visible.

    Reading the table

    For n = 5 the finished table is [0, 1, 2, 4, 8, 16], so the answer is 16. Index 0 stays 0 and is never used, which is why n = 0 is answered before the table exists.

    Complexity

    Time: O(n), one loop with a constant amount of work per step. Space: O(n) for the table, which a single running variable could reduce to O(1).

    Edge cases and common mistakes

    • n = 0 and n = 1. Both return 1. For n = 1 the loop doesn't run.
    • n = 2. Both [1, 2] and [2, 1] are valleys, so the answer is 2.
    • Confusing a valley with "not a peak". The permutation 2 3 1 goes up and then down. It is a peak, not a valley, and it is not counted for n = 3, whose four valleys are 123, 213, 312 and 321.
    • Counting the middle. The largest value can't be placed anywhere except the two ends, which is the whole reason for the factor 2.

    Testing

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