Problem statement
Arrange the distinct values 1..n in every possible order, sort those arrangements lexicographically, and return the one at position k. The position starts at 1, not 0.
For n=3, the order is 123,132,213,231,312,321. This question wants one ranked arrangement. It does not ask for all permutations or impose the alternating-parity rule used in Permutations III.
The official bounds are 1≤n≤9 and 1≤k≤n!. Every value is one decimal digit under these bounds, so concatenating the selected values gives an unambiguous output string.
Constraints & requirements
- CONTRACT
- LeetCode: 1≤n≤9 and 1≤k≤n!. A chosen digit cannot be reused. Convert k to a zero-based offset once, then repeatedly select a factorial-sized block from the sorted unused digits.
Examples 3 test cases
Example 1 Case 1
- Input
n=4; k=9- Output
"2314"
Skip the six permutations beginning with 1; inside the 2-prefix block, skip the two beginning with 21.
Example 2 Case 2
- Input
n=3; k=3- Output
"213"
The order begins 123, 132, 213; the third entry is not obtained by sorting the digits of k.
Example 3 Case 3
- Input
n=3; k=1- Output
"123"
Rank one has zero offset and always chooses the first unused digit.
Hints Optional
01Hint 1
With a first digit fixed, how many ways can the remaining n−1 digits be arranged?
02Hint 2
All permutations with the same prefix form one contiguous lexicographic block.
03Hint 3
Use rank=k−1, choice=rank/block and rank%=block. ArrayList removal costs linear time.
How to think before coding
The phrase kth in sorted order is the important clue. Generating every earlier answer may be unnecessary if we can count them without visiting them.
Imagine a sorted permutation tree. At the root, all arrangements beginning with 1 come before those beginning with 2. Once the first digit is fixed, the other n−1 digits can be arranged in (n−1)! ways.
Ask: “Does my desired rank fall inside the first child’s block, or can I skip that whole block?” Repeat the same question inside the chosen prefix. The final implementation uses a loop because only one child block is ever selected.
Brute force: enumerate in order and count leaves
A straightforward baseline runs ordinary permutation backtracking with ascending unused digits. Count complete arrangements and stop at the kth leaf. There is no need to store all previous permutations.
This is correct, and early stopping helps for a small k. But the worst case still reaches the last of n! leaves. If we already know each child owns (n−1)! leaves, visiting all those leaves just to count them wastes work.
Intuition: choose a block, then a rank inside it
For n=4, fixing the first digit leaves 3!=6 arrangements:
| First digit | One-based positions |
|---|---|
| 1 | 1–6 |
| 2 | 7–12 |
| 3 | 13–18 |
| 4 | 19–24 |
The ninth permutation must begin with 2. We can skip the complete 1-prefix subtree without generating any of its six strings.
Why subtract one from k?
Array indices and block offsets start at zero. Convert once: rank=k−1.
For k=9, rank=8. Integer division 8/6=1 selects unused-list index 1, which contains 2. The remainder 8%6=2 is the new offset inside the 2-prefix block.
Do not subtract one again at the next level. The remainder is already zero-based.
Why remove the selected digit?
All values must appear once. Removing a chosen value keeps the remaining candidates sorted and makes every later list index mean “which unused digit?”
The candidate list is not the original array. After selecting 2, it becomes [1,3,4]; choosing index 1 now means 3, not 2.
Why is 0! equal to 1 here?
After fixing the last digit, there is one possible empty suffix. There are not zero arrangements. Setting factorial[0]=1 gives a final block of size one and avoids division by zero.
Algorithm
- Precompute factorials from
0!throughn!and create sorted unused values1..n. - Convert
kintorank=k−1once. - If
mvalues remain, each next-digit block has(m−1)!permutations. - Select unused-list index
rank/block, append that value and remove it. - Replace rank with
rank%blockand repeat until no value remains.
Java solution
The method validates the published n/k bounds. With n≤9, the factorial table safely uses int. The removal is deliberately an indexed ArrayList.remove, so its shifting cost must appear in the complexity analysis.
import java.util.*;
class Solution {
public static String getPermutation(int n, int k) {
if (n < 1 || n > 9) throw new IllegalArgumentException("n must be 1..9");
int[] factorial = new int[n + 1]; // factorial[i] counts permutations of i distinct values.
factorial[0] = 1; // The empty suffix has exactly one arrangement.
List<Integer> available = new ArrayList<>(); // Sorted unused digits define lexicographic blocks.
for (int value = 1; value <= n; value++) {
factorial[value] = factorial[value - 1] * value; // 9! safely fits in int.
available.add(value); // Input values are exactly 1 through n, with no duplicates.
}
if (k < 1 || k > factorial[n]) throw new IllegalArgumentException("k must be 1..n!");
int rank = k - 1; // Convert the one-based question rank into a zero-based offset ONCE.
StringBuilder answer = new StringBuilder();
while (!available.isEmpty()) { // Each iteration fixes one more output position.
int block = factorial[available.size() - 1]; // Arrangements behind each possible next digit.
int choice = rank / block; // Number of complete equal-sized blocks to skip.
answer.append(available.remove(choice)); // Choose that digit and forbid its reuse.
rank %= block; // Rank is now relative to the chosen prefix, not the original list.
}
return answer.toString(); // ArrayList removal makes this O(n^2), not O(n).
}
public static void main(String[] args) {
System.out.println(getPermutation(4, 9)); // 2314
System.out.println(getPermutation(3, 3)); // 213
System.out.println(getPermutation(3, 1)); // 123
}
}The three invocations print 2314, 213 and 123 on separate lines.
Illustrated dry run
Use n=4,k=9 throughout. This is a block-selection trace, not a claim that the efficient algorithm recursively visits every skipped permutation.

Read the text transcript
Follow the Java, step by step
Example: n = 4, k = 9
What to track: Track sorted available digits, zero-based rank, block=(remaining−1)!, choice and answer. This algorithm skips permutation subtrees instead of entering them; the trace shows every selection.
-
Build factorial counts
Java operationfactorial[0] = 1;Statefactorial=[1,1,2,6,24]; available=[1,2,3,4]; k=9Every first-digit block contains 3!=6 permutations. The empty suffix later uses 0!=1.
-
Translate rank once
Java operationint rank = k - 1;Staterank=8; answer=""One-based position 9 has eight complete permutations before it. All later arithmetic uses this offset.
-
Skip the first six permutations
Java operationint choice = rank / block;Stateblock=6; choice=8/6=1; choose available[1]=2; available=[1,3,4]; answer="2"; rank=8%6=2The 1-prefix block is skipped. We now seek offset 2 inside the six permutations beginning with 2.
-
Skip the 21-prefix block
Java operationanswer.append(available.remove(choice));Stateblock=2; choice=2/2=1; choose 3; available=[1,4]; answer="23"; rank=0Each second-digit choice owns 2!=2 suffix arrangements. Offset 2 skips exactly one such block.
-
Choose the first remaining suffix
Java operationrank %= block;Stateblock=1; choice=0; choose 1; available=[4]; answer="231"; rank=0With one position after this choice, each block has one arrangement. Offset zero selects the first unused digit.
-
Consume the final digit
Java operationreturn answer.toString();Stateblock=0!=1; choose 4; available=[]; answer="2314"There is no division by zero: factorial[0] is 1. Empty available ends the loop and returns the one requested permutation.
Final result: "2314"; all four digits are used exactly once.
At each iteration, write four things before touching the code: the unused list, block size, chosen index and new rank. If your result is off by one, inspect the first conversion from k rather than patching later choices.
Why it works
Equal contiguous blocks: For a fixed prefix, choosing any unused next digit leaves the same number of remaining digits. Each next-digit block has the same factorial size, and sorted next digits put those blocks in lexicographic order.
Correct choice: Dividing the zero-based rank by the block size counts exactly how many complete earlier blocks precede the desired answer.
Correct remainder: Taking the remainder removes those earlier blocks. The same rank invariant now holds within the chosen prefix.
Termination: One unused digit is removed per iteration. After n choices, the unique arrangement at the original requested rank is complete.
Complexity and alternative approaches
| Approach | Time | Extra space | Tradeoff |
|---|---|---|---|
| Ordered backtracking, stop at kth leaf | O(n × n!) worst-case upper bound | O(n) | Simple, but may enumerate nearly every permutation |
| Factorial blocks with ArrayList | O(n²) | O(n) | Skips all other permutations; list removals shift elements |
| Factorial blocks with an order-statistics structure | O(n log n) | O(n) | Faster selection/removal for generalized large inputs; unnecessary complexity for n≤9 |
The returned string itself has O(n) characters. The factorial arithmetic is constant-time under this small fixed numeric range. Do not call the ArrayList version O(n) just because it makes n selections: removing near the front can shift n−1,n−2,... values.
Common mistakes
- Using k directly as a zero-based offset.
- Subtracting one at every iteration rather than once.
- Using
m!instead of(m−1)!for the next-digit block. - Keeping the original rank after choosing a prefix instead of its remainder.
- Failing to remove the selected value, allowing repeated digits.
- Confusing this ranked-permutation contract with parity-constrained permutations.
- Claiming the faster asymptotic order-statistics approach is needed for a nine-digit input.