Permutation Sequence

This page explains Java solution to problem Insert Interval using Permutations.

Problem Statement

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.

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

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

Solution

package com.vc.hard;

import java.util.*;

class PermutationSequence {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new ArrayList<>();
        int[] factorial = new int[n];
        factorial[0] = 1;
        for(int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
            numbers.add(i);
        }
        numbers.add(n);

        //We want kth element, so we skip (k - 1) elements as below
        k--;
        StringBuilder sb = new StringBuilder();
        for(int i = n - 1; i >= 0; i--) {
            int index = k / factorial[i];
            k -= index * factorial[i];
            sb.append(numbers.get(index));
            numbers.remove(index);
        }
        return sb.toString();
    }
}

Time Complexity

O(N)
Where N is number of elements for permutation.

Space Complexity

O(N)