Kth Permutation Sequence Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/kth-permutation-sequence

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given two integers n and k, find the k^th permutation sequence of numbers from 1 to n.

Naive Approach

The naive approach is to generate all the permutations of the sequence, and then print the kth sequence in the list.

Analysis

• Time Complexity: O(n * n!)
• Space Complexity: O(n * n!)

Implementation

C++

vector<string> result;
void permute(string s, string possible) {
	if(s.size() == 0) {
		result.push_back(possible);
		return;
	}
	for(int i = 0; i < s.size(); i++) {
		string left = s.substr(0, i);
		string right = s.substr(i + 1, s.size() - i - 1);
		string total = left + right;
		permute(total, possible + s[i]);
	}
}
string getKthPermutation(int n, int k) {
    string permutation = "";
	result.clear();
	for(int i = 1; i <= n; i++) {
		permutation += to_string(i);
	}
	permute(permutation, "");
	return result[k - 1];
}

Java

class Solution {
	void permute(String s, String possible, ArrayList<String> result) {
		if(s.length() == 0) {
			result.add(possible);
			return;
		}
		for(int i = 0; i < s.length(); i++) {
			String left = s.substring(0, i);
			String right = s.substring(i + 1);
			String total = left + right;
			permute(total, possible + s.charAt(i), result);
		}
	}
	String getKthPermutation(int n, int k) {
	    String permutation = "";
		for(int i = 1; i <= n; i++) {
			permutation += (Integer.toString(i));
		}
		ArrayList<String> result = new ArrayList<>();
		permute(permutation, "", result);
		return result.get(k - 1);
	}
}

Optimal Approach

We know that the total number of possible permutations is n!. Considering k to be 0 - based, we can try to find which number will be in the first position. The number at the first position should be k / (n - 1)! + 1 th integer. We can modify k with this algorithm, and try to find the next numbers at the remaining positions, till we have used up all the numbers.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Implementation

C++

int getFactorial(int n) {
	int factorial = 1;
	for(int i = 2; i <= n; i++) {
		factorial *= i;
	}
	return factorial;
}
string getKthPermutation(int n, int k) {
    string result = "", auxiliary = "";
	for(int i = 1; i <= n; i++) {
		auxiliary += (i + '0');
	}
	long long length = getFactorial(n);
	k--;
	while(!auxiliary.empty()) {
		length /= n;
		long long index = k / length;
		k %= length;
		result += auxiliary[index];
		auxiliary.erase(index, 1);
		n--;
	}
	return result;
}

Java

class Solution {
	long getFactorial(int n) {
		long factorial = 1;
		for(int i = 2; i <= n; i++) {
			factorial *= i;
		}
		return factorial;
	}
	String getKthPermutation(int n, int k) {
	    StringBuilder result = new StringBuilder();
		StringBuilder auxiliary = new StringBuilder();
		for(int i = 1; i <= n; i++) {
			auxiliary.append((char)(i + '0'));
		}
		long length = getFactorial(n);
		k--;
		while(auxiliary.length() > 0) {
			length /= n;
			long index = k / length;
			k %= length;
			result.append(auxiliary.charAt((int)index));
			auxiliary.delete((int)index, (int)index + 1);
			n--;
		}
		return new String(result);
	}
}