Permutation Sequence

LeetCode 60 | Difficulty: Hard

Hard

Problem Description

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 k^th permutation sequence.

Example 1:

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

Example 2:

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

Example 3:

Input: n = 3, k = 1
Output: "123"

Constraints:

- `1 <= n <= 9`

- `1 <= k <= n!`

Topics: Math, Recursion

---

Approach

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 100 ms)

Metric	Value
Runtime	100 ms
Memory	N/A
Date	2018-03-05

Solution

public class Solution {
    public string GetPermutation(int n, int k) {
        List<int> nums = new List<int>();
        for (int i = 1; i <= n; i++)
        {
            nums.Add(i);
        }
        int[] fact = new int[n];
        fact[0] = 1;
        for (int i = 1; i < n; i++)
        {
            fact[i] = fact[i-1]*i;
        }
        k = k-1;
        StringBuilder sb = new StringBuilder();
        for (int i = n; i>0; i--)
        {
            int ind= k/fact[i-1];
            k=k%fact[i-1];
            sb.Append(nums[ind]);
            nums.RemoveAt(ind);     
        }
        return sb.ToString();
    }
}

📜 1 more C# submission(s)

Submission (2018-03-05) — 104 ms, N/A

public class Solution {
    public string GetPermutation(int n, int k) {
        List<int> nums = Enumerable.Range(1,n).ToList();
        int[] fact = new int[n];
        fact[0] = 1;
        for (int i = 1; i < n; i++)
        {
            fact[i] = fact[i-1]*i;
        }
        k = k-1;
        StringBuilder sb = new StringBuilder();
        for (int i = n; i>0; i--)
        {
            int ind= k/fact[i-1];
            k=k%fact[i-1];
            sb.Append(nums[ind]);
            nums.RemoveAt(ind);     
        }
        return sb.ToString();
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.