Permutation Sequence

June 20, 2020

Introduction

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Solution

Let’s use greedy algorithm to fill up the k-th combination. First we need to pre-allocate array of all possible digits. Then on each step we need to get appropriate digit number from array and remove it from array.

func getPermutation(n int, k int) string {
    k--
    var digits []byte
    for i := 1; i <= n; i++ {
        digits = append(digits, '0' + byte(i))
    }

    var out []byte
    for i, j := fact(n), n; j > 1; j-- {
        m := i / j
        d := k / m
        out = append(out, digits[d])
        k -= d * m
        digits = remove(digits, d)
        i = m
    }

    out = append(out, digits...)
    return string(out)
}

func remove(arr []byte, i int) []byte {
    return append(arr[:i], arr[i+1:]...)
}

func fact(n int) int {
    if n == 1 {
        return n
    }
    return n * fact(n-1)
}

Performance of this solution is:

Runtime: 0 ms, faster than 100.00% of Go online submissions for Permutation Sequence.
Memory Usage: 2 MB, less than 91.84% of Go online submissions for Permutation Sequence.

comments powered by Disqus

Do you want to know me more private?→Click!

span class="p">{ health[i][j] += dungeon[i][j] } } } return health[n-1][m-1] > 0 } func max(a, b int) int { if a > b { return a } return b }

Performance of this solution is:

Runtime: 28 ms
Memory Usage: 3.7 MB

Let’s move princess instead of king, so in this case we can track min health required for king to come to particular cell.

func calculateMinimumHP(dungeon [][]int) int {
    n := len(dungeon)
    if n == 0 {
        return -1
    }
    m := len(dungeon[0])
    health := make([][]int, n)
    for i := 0; i < n; i++ {
        health[i] = make([]int, m)
    }
    health[n-1][m-1] = minHealth(1, dungeon[n-1][m-1])
    for j := m-2; j >= 0; j-- {
        health[n-1][j] = minHealth(health[n-1][j+1], dungeon[n-1][j])
    }
    for i := n-2; i >= 0; i-- {
        health[i][m-1] = minHealth(health[i+1][m-1], dungeon[i][m-1])
        for j := m-2; j >= 0; j-- {
            optA := minHealth(health[i+1][j], dungeon[i][j])
            optB := minHealth(health[i][j+1], dungeon[i][j])
            health[i][j] = min(optA, optB)
        }
    }
    return health[0][0]
}

func minHealth(health, cell int) int {
    h := health - cell
    if h <= 0 {
        return 1
    }
    return h
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

This solution is faster and gives good performance:

Runtime: 4 ms
Memory Usage: 3.7 MB

comments powered by Disqus

Do you want to know me more private?→Click!