Start learning free

LESSON 342 OF 415 · DYNAMIC PROGRAMMING

Valley Permutations in Swift: Counting with a dp Array

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

    SWIFT · DYNAMIC PROGRAMMING

    Valley Permutations in Swift, explained

    Problem overview

    The method countPermutations receives a length n and returns how many valley permutations of the numbers 1 to n exist. A valley permutation is a concatenation of two parts: a decreasing sequence followed by an increasing one. Either part may be empty, so a fully increasing or fully decreasing permutation counts too. The notes limit n to 12.

    For n = 4 there are eight: [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]. Only the count is returned.

    Approach: the largest number sits at an end

    A valley permutation goes down to its smallest element and then up. Its largest element can't be anywhere in the middle, because then it would have smaller neighbours on both sides, which makes a peak, not a valley. So the largest number i is always the first or the last element.

    That gives a recurrence. Take any valley permutation of length i - 1 and add the new largest number i to the front or to the back. Both results are valleys: at the front it extends the decreasing part, at the back it extends the increasing part. And removing i from either end of a valley permutation of length i leaves a valley permutation of length i - 1, so every longer one is reached this way, and from exactly one shorter one and one choice of end. Each shorter permutation therefore gives exactly two longer ones:

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

    The base case is a single number, dp[1] = 1. The table runs 1, 2, 4, 8, which matches the eight permutations for n = 4; in general the answer is 2 to the power n - 1.

    Check it on the example. The valley permutations of length 3 are [1, 2, 3], [2, 1, 3], [3, 1, 2] and [3, 2, 1]: four of them. 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]. These are the eight permutations listed above, with no repeats, because a permutation that starts with 4 can't also end with 4 when its length is above 1.

    The same reasoning shows why the length-1 case is special: a single number is both the front and the back, and it is counted once. That is why the table starts at dp[1] = 1 and doubles only from length 2.

    Why not generate them

    The direct approach would build every permutation of length n and test each for the valley shape. With n = 12 that means checking 479001600 permutations, each needing a scan of 12 elements. The recurrence reaches the same answer in 11 multiplications, because it counts the valleys without ever listing them. This is the main idea of dynamic programming: express the answer for a size through the answer for a smaller size, then fill a table from the smallest size up.

    Step by step

    1. Handle n = 0 first. The empty permutation is the only permutation of length 0, and it counts as a valley because both of its parts are empty, so the answer is 1. This also protects the code below: for n = 0 the table has no dp[1].
    2. Create the table: a var array dp of n + 1 zeros, [Int](repeating: 0, count: n + 1).
    3. Set the base case: dp[1] = 1.
    4. Loop over the lengths with i in 2..<(n + 1), which stops before n + 1, so i reaches n.
    5. Double the previous entry: dp[i] = 2 * dp[i - 1].
    6. Return dp[n].

    The solution in Swift

    class Solution {
    func countPermutations(_ n: Int) -> Int {
        if n == 0 {
            return 1
        }
        var dp = [Int](repeating: 0, count: n + 1)
        dp[1] = 1
        for i in 2..<(n + 1) {
            dp[i] = 2 * dp[i - 1]
        }
        return dp[n]
    }
}

    Swift details worth knowing:

    • Why the early return matters. With n = 0 the array has a single element, so dp[1] = 1 would be out of range, and a range with a lower bound above its upper bound (2..<1) crashes in Swift as well. The guard avoids both.
    • n = 1 needs no guard. The range 2..<2 is empty, so the loop is skipped and dp[1] is returned.
    • Overflow. The values are powers of two, at most 2048 here. Swift's Int is 64 bits, and an overflow would stop the program rather than wrap, but that is far away.

    Complexity

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

    Space: O(n), for the table. Keeping only the previous value would reduce it to O(1).

    The closed form also explains the table. Each of the n - 1 numbers from 2 to n has two places to go, front or back of the arrangement built so far, while 1 simply starts it: that is 2^(n - 1) choices in total, 2048 for n = 12.

    Edge cases and common mistakes

    • n = 0. The answer is 1, from the early return.
    • n = 1. The answer is 1.
    • n = 2. Both [1, 2] and [2, 1] qualify, so the answer is 2.
    • Counting all permutations. Using i * dp[i - 1] counts factorials, which is 24 for n = 4, not 8.
    • Forgetting that the largest number can go on either side. Counting only one end gives 1 for every length.

    Testing

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