Start learning free

LESSON 270 OF 348 · BACKTRACKING

Generate Valley Permutations in TypeScript: Bitmask Enumeration

Practice O(n!) Read the full explanation

Given a non-negative integer n, return all the 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.

E.g. valley permutations follow this format: [p[0] < p[1] < p[2] < ... < p[k] > p[k+1] > p[k + 2] > ... > p[n]].


Example:

Input: n = 4

Output:[
    [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]
]

Explanation:
Permutations suchs as [1, 4, 2, 3] are not valley because 1 < 4 > 2 < 3

Notes: n <= 10


STEP 1 OF 9
    Ctrl + Enter to check

    TYPESCRIPT · BACKTRACKING

    Generate Valley Permutations in TypeScript, explained

    Problem overview

    The method generateValleyPermutations receives a non-negative integer n and returns every valley permutation of the numbers 1 to n as a number[][]. A valley permutation first decreases and then increases, like a valley between two slopes. The lowest point of the valley is always the value 1.

    For n = 4 there are eight of them, in this order: [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]. A permutation such as [1, 4, 2, 3] is not a valley: it goes up, down and up again, so it has a peak in the middle.

    Approach: choose a side for every value

    The brute-force idea generates all n! permutations and keeps the ones shaped like a valley. For n = 10 that is 3,628,800 permutations to build and test, when only 512 of them qualify.

    It is faster to build only valid ones. Since the sequence falls and then rises, the smallest value, 1, must sit at the bottom. Every other value from 2 to n is either on the falling slope to the left of 1 or on the rising slope to the right. Once you decide the side of each value, the permutation is fixed: the left values are written in decreasing order, then 1, then the right values in increasing order.

    Each of the n - 1 values from 2 to n has two choices, so there are 2^(n - 1) valley permutations, and each one corresponds to exactly one set of choices.

    A bitmask is a convenient way to enumerate all those choices. Count mask from 0 up to 2^(n - 1) - 1. Written in binary, every number in that range is a different pattern of n - 1 bits. Bit i of the mask decides the side of value i + 2: set means left, clear means right.

    For n = 4 and mask = 5 (binary 101), bit 0 is set, bit 1 is clear and bit 2 is set. So 2 and 4 go left, 3 goes right. Sorting the left side in decreasing order gives [4, 2], so the permutation is [4, 2, 1, 3].

    Step by step

    1. Create result as a const typed number[][]. The annotation is needed because TypeScript can't work out the element type from an empty array literal.
    2. Loop over every mask from 0 up to (1 << (n - 1)) - 1. Shifting 1 left by k places gives 2^k, so this visits all 2^(n - 1) bit patterns.
    3. Create fresh left and right arrays inside the loop, so that each mask starts from empty slopes. const only forbids reassigning the variable; pushing into the array is still allowed.
    4. Loop over the bits with i from 0 to n - 2. That is n - 1 iterations, one per value from 2 to n.
    5. Compute the value the bit controls: val = i + 2. The offset is 2 because value 1 needs no bit.
    6. Test the bit. (mask >> i) & 1 moves bit i into the lowest position and masks out everything else. The result is 0 or 1, so it works directly as an if condition. Push val to left if the bit is set, otherwise to right.
    7. Sort the slopes. left goes in descending order, so it falls toward 1, and right in ascending order, so it rises away from 1. Both need a comparator, as explained below.
    8. Join the pieces with concat: left, then [1], then right. Push the new array to result.
    9. Return result after the outer loop has finished.

    The solution in TypeScript

    class Solution {
    generateValleyPermutations(n: number): number[][] {
        const result: number[][] = []
        for (let mask = 0; mask < (1 << (n - 1)); ++mask) {
            const left: number[] = []
            const right: number[] = []
            for (let i = 0; i < n - 1; ++i) {
                const val = i + 2
                if ((mask >> i) & 1) {
                    left.push(val)
                } else {
                    right.push(val)
                }
            }
            left.sort((a, b) => b - a)
            right.sort((a, b) => a - b)
            const perm = left.concat([1]).concat(right)
            result.push(perm)
        }
        return result
    }
}

    The TypeScript and JavaScript details worth a closer look:

    • Sort needs a comparator. Without one, sort() converts the elements to strings and compares those. [10, 9, 1].sort() gives [1, 10, 9], which is wrong for numbers. (a, b) => b - a sorts descending and (a, b) => a - b ascending. Both slopes were filled in increasing order of value, so right is already ascending, but the explicit sort states the intention.
    • sort works in place. It changes left and right themselves, which is fine because they are rebuilt for each mask.
    • concat returns a new array. left.concat([1]) doesn't modify left, so the two calls can be chained. The result has the type number[].
    • Bit operators work on 32-bit integers. number is a double, but <<, >> and & first convert their operands to 32-bit integers. That is plenty here, because n is at most 10.
    • Types are erased. The number[][] annotation helps the compiler and the editor, but nothing checks it when the program runs.

    Complexity

    Time: O(n * 2^n). There are 2^(n - 1) masks. For each one the inner loop does n - 1 steps, sorting two arrays with a total of n - 1 elements costs at most O(n log n), and concat copies n elements. The sort dominates, so strictly the total is O(n log n * 2^n). The arrays are tiny for n up to 10, so this is fast in practice.

    Space: O(n * 2^n). The output alone holds 2^(n - 1) arrays of length n. Apart from the output, the method uses only O(n) memory for left, right and perm.

    Edge cases and common mistakes

    • n = 1. The loop runs for mask = 0 only, because 1 << 0 is 1. Both slopes stay empty and the result is [[1]].
    • n = 2. One bit gives two masks and the result [[1, 2], [2, 1]].
    • n = 0. The shift 1 << -1 uses only the low five bits of the count, so it computes 1 << 31, which is the negative number -2147483648. The loop condition is false at once and the method returns []. That is a reasonable answer for no values, and it is the one the code gives.
    • Sorting without a comparator. For n from 10 and up, values such as 10 and 9 would be ordered as strings and the slopes would be wrong.
    • Sharing the arrays between masks. Declaring left and right outside the outer loop would mix the values of different masks.
    • Starting the bit values at 1. The value 1 is never assigned to a side. Using val = i + 1 would put 1 on a slope and leave n out.
    • Order of the output. Counting masks upward gives the order shown in the example, where the position of 2 changes fastest. A different loop would produce the same permutations in another order.

    Testing

    • n = 1 gives [[1]].
    • n = 2 gives [[1, 2], [2, 1]].
    • n = 3 gives [[1, 2, 3], [2, 1, 3], [3, 1, 2], [3, 2, 1]].
    • n = 4 gives the eight permutations listed in the overview.
    • n = 10 gives 512 permutations.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free