LESSON 317 OF 348 · DYNAMIC PROGRAMMING

Valley Permutations in TypeScript: Doubling with DP

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

Guided

Ctrl + Enter to check

TYPESCRIPT · DYNAMIC PROGRAMMING

Valley Permutations in TypeScript, explained

Problem overview

The method countPermutations receives a non-negative integer n and returns how many valley permutations of length n exist. A permutation of the numbers 1 to n is a valley permutation when it is a decreasing run followed by an increasing run. Either run may be empty, so a fully increasing or a fully decreasing permutation counts too.

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]. The answer is 8. The statement limits n to 12. Out of the 24 permutations of length 4, only these 8 have the valley shape; [1, 3, 2, 4], for example, goes up, down and up again.

Approach: the largest number sits at an end

The number 1 always sits at the bottom of the valley, where the decreasing run turns into the increasing one. Everything to its left is decreasing and everything to its right is increasing, so a valley permutation is decided by which of the other numbers go to the left of 1; the rest go to the right. Counting those choices directly gives the same answer, but the lesson uses a recurrence that is easier to follow.

In a valley, the sequence only goes down and then up, so its largest value can't be in the interior: a value with a neighbour on each side that is smaller would be a peak, and a valley has none. The largest number, i, must therefore be the first or the last element.

Remove it and what remains is a valley permutation of length i - 1. Going the other way, put i at the front or at the back of any valley permutation of length i - 1, and the result is a valley again. (Placing the maximum first just extends the decreasing run, and placing it last extends the increasing run.) For i of 2 or more, the two placements give different permutations, so each shorter valley permutation produces exactly two longer ones:

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

Here is the step from length 3 to length 4. The valley permutations of length 3 are [1, 2, 3], [2, 1, 3], [3, 1, 2] and [3, 2, 1]. Putting 4 in front of each gives [4, 1, 2, 3], [4, 2, 1, 3], [4, 3, 1, 2] and [4, 3, 2, 1]. Putting 4 at the back gives [1, 2, 3, 4], [2, 1, 3, 4], [3, 1, 2, 4] and [3, 2, 1, 4]. That is exactly the list of eight in the example, with no repeats.

The base case is dp[1] = 1, since a single number is one valley permutation. The table is 1, 2, 4, 8, and in closed form the answer is 2 ** (n - 1) for n of at least 1. The case n = 0 doesn't fit the table, so it is answered separately.

Step by step

Handle n = 0. Compare with === and return 1: the empty permutation is the only one of length 0, and it counts as a valley because both runs are empty. The table starts at dp[1], which doesn't exist for n = 0.
Declare dp as a number[] of length n + 1, created with new Array(n + 1).fill(0).
Set the base case: dp[1] is 1.
Loop with i, declared with let, from 2 to n inclusive.
Double: dp[i] is 2 * dp[i - 1], because the largest number goes first or last.
Return dp[n].

The solution in TypeScript

class Solution {
    countPermutations(n: number): number {
        if (n === 0) {
            return 1;
        }
        const dp: number[] = new Array(n + 1).fill(0);
        dp[1] = 1;
        for (let i = 2; i <= n; i++) {
            dp[i] = 2 * dp[i - 1];
        }
        return dp[n];
    }
}

TypeScript details worth knowing:

new Array(n + 1) alone creates empty slots, not zeros. The call to fill(0) writes a zero into every slot. Here the loop overwrites every slot it reads anyway, but zeros are the safe starting value for a table.
=== is the strict comparison. It never converts types, so n === 0 is true only for the number 0. The loose == would also treat "0" and false as 0.
const for the table. The variable is never reassigned; its contents still change, because const only fixes the binding.
Type annotations are erased when the code is compiled to JavaScript. They don't check the value of n at run time.
No overflow. The values are doubles, and the largest answer here, for n = 12, is 2048.

Complexity

Time: O(n). One multiplication per pass of the loop.

Space: O(n). The table has n + 1 entries. A single running value would reduce this to O(1).

Edge cases and common mistakes

n = 0. Without the early return, dp[1] = 1 would grow an array of length 1 and the function would read dp[0], which is 0 after fill. The answer would be 0 instead of 1.
n = 1. The loop doesn't run, and the answer is 1.
n = 2. Both [1, 2] and [2, 1] are valleys, so the answer is 2.
Thinking the smallest number is the one at the end. The smallest number sits at the bottom of the valley, which can be anywhere. It is the largest that is forced to an end.
Counting all permutations. Using i * dp[i - 1] gives factorials: 24 instead of 8 for n = 4.
Starting the loop at 1. That would overwrite the base case with 2 * dp[0], which is 0.

Testing

n = 0 gives 1.
n = 1 gives 1.
n = 2 gives 2.
n = 4 gives 8.
n = 12 gives 2048.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free