Kth Permutation Sequence | Math + Greedy

leetcode.com

Problem Statement

Given two integers n and k, return the kth permutation sequence of numbers from 1 to n.

Example:

n = 3
k = 3

Permutations:

123
132
213
231
312
321

Output:

213

---

Brute Force Intuition

Generate all permutations using backtracking.

Store them in a list and return:

list.get(k - 1)

Since permutations are generated in lexicographical order.

Complexity

• Time Complexity: O(N! × N)
• Space Complexity: O(N! × N)

Brute Force Snippet

generateAllPermutations();

return permutations.get(k - 1);

---

Moving Towards the Optimal Approach

Generating all permutations is wasteful.

Consider:

n = 4

Total permutations:

4! = 24

Observe:

Starting with 1 → 3! = 6 permutations
Starting with 2 → 3! = 6 permutations
Starting with 3 → 3! = 6 permutations
Starting with 4 → 3! = 6 permutations

Each first digit forms a block of:

(n - 1)!

permutations.

Instead of generating everything, we directly identify which block contains the kth permutation.

---

Pattern Recognition

Whenever you see:

• Kth permutation
• Kth arrangement
• Lexicographical ordering

Think:

Factorial Number System

---

Key Observation

For:

n = 4
k = 9

Numbers:

[1,2,3,4]

Block Size:

(4-1)! = 6

Blocks:

1xxxx → 6 permutations
2xxxx → 6 permutations
3xxxx → 6 permutations
4xxxx → 6 permutations

Since:

k = 9

Skip first block:

k = 9 - 6 = 3

So first digit becomes:

2

Now solve the same problem for:

[1,3,4]
k = 3

---

Optimal Idea

Convert k into zero-based indexing:

k--;

At every step:

index = k / factorial

Choose the element at that index.

Update:

k = k % factorial

Remove chosen number and continue.

---

Optimal Java Solution

import java.util.*;

class Solution {

    public String getPermutation(int n, int k) {

        List<Integer> numbers = new ArrayList<>();

        int fact = 1;

        for (int i = 1; i < n; i++) {
            fact *= i;
        }

        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }

        k--;

        StringBuilder ans = new StringBuilder();

        while (true) {

            ans.append(numbers.get(k / fact));

            numbers.remove(k / fact);

            if (numbers.size() == 0)
                break;

            k %= fact;

            fact /= numbers.size();
        }

        return ans.toString();
    }
}

---

Dry Run

Input

n = 3
k = 3

Numbers:

[1,2,3]

Factorial:

2! = 2

Convert:

k = 2

---

Step 1

index = 2 / 2 = 1

Choose:

2

Remaining:

[1,3]

Update:

k = 2 % 2 = 0
fact = 1

---

Step 2

index = 0 / 1 = 0

Choose:

1

Remaining:

[3]

---

Step 3

Choose:

3

Result:

213

---

Why This Works?

Each digit contributes a fixed number of permutations:

(n-1)!

Instead of generating all permutations, we directly jump to the block containing the kth permutation.

This reduces complexity drastically.

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N²)
Space Complexity	O(N)

The remove() operation in ArrayList costs O(N).

---

Interview One-Liner

Treat permutations as blocks of size (n-1)!. Use factorial math to directly determine which digit belongs at each position without generating all permutations.

---

Pattern Learned

Generate All Permutations


Use Factorial Blocks

Similar Problems

• Kth Permutation Sequence
• Lexicographical Kth Number
• Ranking Permutations
• Factorial Number System

---

Memory Trick

Think:

1234

1xxx → 6 permutations
2xxx → 6 permutations
3xxx → 6 permutations
4xxx → 6 permutations

Find:

Which block contains k?

Pick that digit, remove it, and repeat.

Mental Model

Subsets
→ Pick / Not Pick

Palindrome Partitioning
→ Try Every Cut

Kth Permutation
→ Find Correct Block Using Factorials

Once you hear:

"Return the kth permutation"

your brain should immediately think:

Factorials + Block Selection, not Backtracking.