Permutation Sequence LeetCode Solution | Easy Approach

Minimum Cost to Merge Stones
Share:

Permutation Sequence | 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:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth 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!

Permutation Sequence Solutions

Time: O(n)
Space: O(n)

C++

class Solution {
 public:
  string getPermutation(int n, int k) {
    string ans;
    vector<int> nums(n);
    vector<int> factorial(n + 1, 1);  // factorial[i] := i!

    iota(begin(nums), end(nums), 1);

    for (int i = 2; i <= n; ++i)
      factorial[i] = factorial[i - 1] * i;

    --k;  // 0-indexed

    for (int i = n - 1; i >= 0; --i) {
      const int j = k / factorial[i];
      k %= factorial[i];
      ans += to_string(nums[j]);
      nums.erase(begin(nums) + j);
    }

    return ans;
  }
};

Java

 class Solution {
  public String getPermutation(int n, int k) {
    StringBuilder sb = new StringBuilder();
    List<Integer> nums = new ArrayList<>();
    int[] factorial = new int[n + 1]; // factorial[i] := i!

    for (int i = 1; i <= n; ++i)
      nums.add(i);

    Arrays.fill(factorial, 1);
    for (int i = 2; i <= n; ++i)
      factorial[i] = factorial[i - 1] * i;

    --k; // 0-indexed

    for (int i = n - 1; i >= 0; --i) {
      final int j = k / factorial[i];
      k %= factorial[i];
      sb.append(nums.get(j));
      nums.remove(j);
    }

    return sb.toString();
  }
}

Python

class Solution:
  def getPermutation(self, n: int, k: int) -> str:
    ans = ''
    nums = [i + 1 for i in range(n)]
    factorial = [1] * (n + 1)  # factorial[i] := i!

    for i in range(2, n + 1):
      factorial[i] = factorial[i - 1] * i

    k -= 1  # 0-indexed

    for i in reversed(range(n)):
      j = k // factorial[i]
      k %= factorial[i]
      ans += str(nums[j])
      nums.pop(j)

    return ans

Watch Tutorial

Checkout more Solutions here

Leave a Comment

Your email address will not be published. Required fields are marked *

x