Start learning free

LESSON 341 OF 414 · DYNAMIC PROGRAMMING

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

    RUST · DYNAMIC PROGRAMMING

    Valley Permutations in Rust, explained

    Problem overview

    The function count_permutations takes n and returns the number of valley permutations of length n. A permutation of 1 through n is a valley when it is a decreasing run followed by an increasing run. Either run may be empty or have a single element. The statement limits N to 12.

    For n = 4 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]. There are 8. The other 16 permutations of four numbers, such as [1, 3, 2, 4], go up and come back down, which a valley never does.

    Approach: place the largest number at one end

    In a valley, the values fall to a minimum and then rise. The smallest value, 1, is the bottom of the valley, and the largest value, i, can't be in the middle: a number with neighbours on both sides that are smaller would make a peak. So i must be at the very beginning or at the very end.

    Remove it, and what is left is a valley permutation of length i - 1: taking an end element off a decreasing-then-increasing sequence leaves one. The step also reverses. Take any valley of length i - 1 and put i in front: the decreasing part just gets longer, or begins with it. Put i at the back, and the increasing part grows. Both results are valleys, and for i > 1 they are different permutations, since i is in different places. So each shorter permutation gives exactly two longer ones:

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

    Here is the step from length 2 to length 3. The valleys of length 2 are [1, 2] and [2, 1]. Putting 3 in front of each gives [3, 1, 2] and [3, 2, 1], and putting 3 at the back gives [1, 2, 3] and [2, 1, 3]. That is four valleys. The only two permutations of 1, 2, 3 left out are [1, 3, 2] and [2, 3, 1], which have 3 in the middle, and neither is a valley.

    One detail makes the argument precise: removing the largest value leaves the other i - 1 values, which are exactly 1 through i - 1, so the remaining permutation is a plain permutation of that length and the same rule applies to it again.

    The base case is dp[1] = 1: a single number is one valley. The table is 1, 2, 4, 8, matching the example: dp[4] = 8.

    Step by step

    1. Answer n = 0 directly. If n is 0, return 1 with an explicit return and a semicolon, as an early exit needs. The empty permutation counts as a valley, since both of its runs are empty. The table below starts at dp[1], which doesn't exist when n is 0.
    2. Create dp with vec![0i32; n + 1]. The starting code has already converted n to a usize.
    3. Set dp[1] = 1.
    4. Loop over 2..=n.
    5. Double: dp[i] = 2 * dp[i - 1].
    6. Return dp[n] as the final expression.

    The solution in Rust

    impl Solution {
    fn count_permutations(n: i32) -> i32 {
        let n = n as usize;
        if n == 0 {
            return 1;
        }
        let mut dp = vec![0i32; n + 1];
        dp[1] = 1;
        for i in 2..=n {
            dp[i] = 2 * dp[i - 1];
        }
        dp[n]
    }
}

    The Rust details worth a closer look:

    • Early return against the final expression. The return 1; inside the if leaves the function at once. The last line, dp[n], has no semicolon, so it is the value returned otherwise.
    • Shadowing. let n = n as usize; replaces the i32 parameter with a usize of the same name, which is the type vectors need for sizes and indices.
    • Overflow. The largest answer is dp[12] = 2048, far below the i32 limit. The table would overflow only at n = 32, where the value would be 2^31.
    • Why the guard matters. For n = 0 the vector has length 1, and dp[1] = 1 would panic with an index out of bounds.

    Complexity

    Time: O(n). One multiplication per length.

    Space: O(n). The table holds n + 1 entries. The answer is just 2^(n - 1) for n >= 1, but the table shows where it comes from.

    Edge cases and common mistakes

    • N = 0. Returns 1 from the guard.
    • N = 1. Returns 1, and the loop is skipped.
    • N = 2. Returns 2: [1, 2] is all increasing and [2, 1] is all decreasing, and both are valleys.
    • Treating a single-run permutation as invalid. A fully increasing or fully decreasing permutation is a valley. One of the two parts is just empty.
    • Counting all permutations. Using i * dp[i - 1] counts every ordering and gives 24 for n = 4.
    • Placing the smallest number instead. The smallest number is the bottom of the valley and can sit at any position, so it gives no simple rule. The largest number is the one with only two possible places.

    Testing

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