Permutation Sequence (LeetCode 60)
You will see how the k-th arrangement in dictionary order is built one digit at a time by skipping whole blocks of arrangements, without listing any of them.
The numbers 1, 2, ..., n can be put in order in n! different ways. Write all of these arrangements as strings and sort them the way a dictionary sorts words. For n = 3 the list is "123", "132", "213", "231", "312", "321", and its entries are numbered from 1.
Given n and a position k in this list, return the arrangement at position k.
Worked Examples
n = 3, k = 3"213"n = 4, k = 9"2314"n = 3, k = 1"123"⚖️Formal Constraints & Bounds
1 <= n <= 91 <= k <= n!
Why It Works & Core Invariant
Arrangements in dictionary order come in equal blocks, one per unused digit, so the k-th one is read digit by digit: skip k // block whole blocks, keep k % block, and shrink to the next slot.
Real-World Scenario & Production Applications
Rubik's Cube solvers such as Herbert Kociemba's two-phase algorithm turn an arrangement of the cube's pieces into one number, its rank in dictionary order, and turn numbers back into arrangements, so their lookup tables can be plain arrays indexed by that number. Turning a rank back into an arrangement is exactly this problem.
Subproblems & Recurrence Decomposition3 Phases
m different digits have m! orders. With the table fact, each slot's block size is a lookup: every unused digit starts a block of fact[n - 1 - slot] arrangements.
fact = [1] * n
for m in range(1, n):
fact[m] = fact[m - 1] * mStep-by-Step Execution Trace Table
The debugger's first preset, n = 3, k = 3 (LeetCode Example 1, the trap case), with fact = [1, 1, 2] and k = 2 after k -= 1:
| Slot | block | index = k // block | k after k %= block | pool before | Digit taken | result |
|---|---|---|---|---|---|---|
| 0 | fact[2] = 2 | 2 // 2 = 1 | 0 | ['1', '2', '3'] | '2' | ['2'] |
| 1 | fact[1] = 1 | 0 // 1 = 0 | 0 | ['1', '3'] | '1' | ['2', '1'] |
| 2 | fact[0] = 1 | 0 // 1 = 0 | 0 | ['3'] | '3' | "213" |
Without k -= 1, slot 0 would still take '2' (3 // 2 = 1) but leave k = 1, and slot 1 would compute 1 // 1 = 1 and take '3': one block too far, ending at "231".
| 1 | The arrangements in dictionary order come in blocks, one per first digit, each with `(n - 1)!` arrangements: skip whole blocks instead of listing them. |
| 2 | Keep this true: after `k -= 1`, `k` is the number of arrangements that start with `result` and come before the answer. |
| 3 | The shape: a factorial table; `k -= 1`; for each slot, `block = fact[n - 1 - slot]`, `index = k // block`, `k %= block`, and `pool.pop(index)` onto the result. |
| 4 | The trap: `k` counts from 1. Without `k -= 1`, a `k` that is a multiple of `block` picks one block too far: `n = 3, k = 3` gives `"231"` instead of `"213"`. |
Target: Permutation Sequence (LeetCode 60). `fact[m]` is how many orders `m` different digits have. Building the table once keeps every block size a lookup.
Boundary pointers contract inward after each directional sweep; modular arithmetic bounds state cyclically.
while top <= bottom and left <= right: sweep right, down, left, up, contracting respective pointer.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Listing all n! arrangements to read the k-th one is hopeless for large k. But a list in dictionary order is made of blocks: every arrangement that starts with 1 comes first, then every one that starts with 2, and so on, and each block holds (n - 1)! arrangements. Count and Skip never lists anything: it asks how many whole blocks come before the answer, k // block, jumps over them, and repeats the question inside the block it landed in, one slot further right and one factorial smaller.
📚 The Analogy: Finding Page k in a Set of Volumes
An encyclopedia comes in volumes of exactly 500 pages each. To open page 1,730 you do not leaf through from page 1: 1,729 pages come before it, which is 3 whole volumes (1,500 pages) and 229 pages more, so you take volume 4 and open its page 230. Each slot of an arrangement is one more level of volumes: the first digit picks the volume, the second digit the chapter, and so on.
🪄 The Mathematical Harmony / Magic Trick
k -= 1for slot in range(n): block = fact[n - 1 - slot] index = k // block k %= block result.append(pool.pop(index)) After k -= 1, k counts the arrangements that come before the answer. The blocks at a slot come in the same order as the unused digits in pool and all have block arrangements, so exactly index = k // block of them lie before the answer, and k % block is where the answer sits inside its own block. The digits written this way, index at each slot, are the factorial number system: k in a base that is (n - 1)!, then (n - 2)!, and so on.
💡 Summary
Subtract 1 from k, then at each slot skip k // block whole blocks, keep k % block, and take that digit out of the pool. n slots, each with an O(n) pop: time and space, whatever k is.
The 1-based rank:
k -= 1before the loop:kcounts from 1, and without it everykthat is a multiple ofblockpicks one block too far:n = 3, k = 3gives"231"instead of"213".Block size:
block = fact[n - 1 - slot], notfact[n - slot]: a block holds the arrangements of the slots after this one, one factorial smaller than the number of digits still unused.Removing the used digit:
pool.pop(index), notpool[index]: the chosen digit must leave the pool, or the next slot counts it again and the answer repeats a digit.Blocks of different sizes: When the blocks at a slot have different sizes, as in Kth Smallest Instructions (LC 1643) or K-th Smallest in Lexicographical Order (LC 440), compare
kwith each choice's own count in order and subtract the counts you skip:k // blockonly works when every block at a slot is the same size.
4-Phase Thought Process Model
You will see how a senior engineer turns "the arrangement at position k" into skipping whole blocks, and says so out loud.
Pattern Recognition Signals
The 10-second spot
"All of these arrangements ... sort them the way a dictionary sorts words", "its entries are numbered from 1" and "return the arrangement at position k", with k up to n!: a rank in a sorted list far too long to build. That is the signal for Count and Skip: count how many arrangements each choice covers and jump over whole blocks.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After k -= 1, k is the number of arrangements that start with result and come before the answer. At each slot every unused digit starts a block of block = fact[n - 1 - slot] arrangements, so index = k // block blocks are skipped, pool.pop(index) is the digit, and k %= block is the rank inside that block.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
k -= 1first:kis 1-based, and without it akthat is a multiple ofblockpicks one block too far, son = 3, k = 3gives"231"instead of"213".block = fact[n - 1 - slot], notfact[n - slot]: a block holds the orders of the slots after this one.index = k // blockbeforek %= block: the modulo replacesk, so the other order always picks index 0.pool.pop(index), notpool[index]: the used digit must leave the pool, or the next slot counts it again and a digit repeats.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Count and Skip. Listing all n factorial arrangements is far too slow, but in dictionary order they come in blocks: every arrangement that starts with the same digit sits together, and each block has n minus one factorial members. First I subtract one from k, so it counts the arrangements before the answer. Then for each slot, block is the factorial of the slots still to fill after this one, k divided by block is how many whole blocks I skip, so that index into the unused digits is this slot's digit, and k mod block is the rank inside that block. I pop the digit out of the pool so it isn't used twice. The trap is the one-based k: without subtracting one, a k that's a multiple of the block size lands one block too far. That's n slots with an
O(n)pop each, so O(N squared) time andO(N)space.
So: k -= 1, k // block blocks skipped and k % block kept at each slot, the used digit popped; O(N^2) time, O(N) space.
Complexity & Mathematical Proof
O(N^2)
Count the work in getPermutation. Building fact runs N - 1 multiplications. The for slot in range(n) loop runs N times; each pass does one lookup, one division, one modulo and one pool.pop(index). The division and modulo are O(1) (all values fit below 9! = 362,880), but pop from the middle of a list shifts the digits after it, up to N - 1 of them. So each slot costs O(N), and N slots cost O(N^2). The "".join at the end is O(N). The number of steps never depends on k; only the cost of each pop does, and it is at most O(N).
O(N)
fact, pool and result each hold at most N items, plus a few integers (k, slot, block, index): O(N). There is no recursion. The returned string has N characters and is counted in the same O(N).
T(N) = (N - 1) table steps + N slots · O(N) pop = O(N^2)
Derivation Progression
N - 1
for m in range(1, n) does one multiplication per entry.
N
for slot in range(n) fixes one digit per pass.
O(N)
k // block and k %= block are O(1); pool.pop(index) shifts up to N - 1 digits.
O(N^2)
N passes of O(N) work, whatever k is.
Variable Definitions
n, the number of digits arranged (at most 9)
Memory Architecture & Bounds
O(1): one call, no recursion
O(N): fact, pool and result
O(N): the returned string of N digits
Boundary Best / Worst Cases
: for the last arrangement every index is the end of pool, so each pop is O(1)
: for the first arrangement every index is 0, and each pop(0) shifts the rest of pool
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "sort them the way a dictionary sorts words", "numbered from 1", "the arrangement at position k". A rank in a sorted list of arrangements far too long to build: Count and Skip, whole blocks of equal size skipped one slot at a time.
n <= 9, so there are at most arrangements and k fits easily in 32 bits. Generating arrangements up to the k-th costs up to steps; Count and Skip needs 9 slots.
With larger n (or multisets, as in Minimum Number of Operations to Make String Sorted (LC 1830)) the block sizes grow past 64 bits: use arbitrary-precision integers, a modulus when only a count is wanted, or cap the sizes at k when only the k-th item is wanted. Decoding many ranks against the same n can share one factorial table.
Core Algorithmic State Invariants
- Equal Blocks per Slot
Every unused digit starts a block of fact[n - 1 - slot] arrangements, and the blocks come in the order of the digits in pool. The answer's digit is decided by how many whole blocks lie before it.
- Count From 0
k -= 1 turns the 1-based position into the number of arrangements before the answer. Without it, n = 3, k = 3 takes one block too many at the second slot and returns "231".
- Divide, Keep the Rest, Remove the Digit
index = k // block, then k %= block, then pool.pop(index): N slots with an O(N) pop each, O(N^2) time and O(N) space, whatever k is.
Permutation Sequence (LeetCode 60)
You will see how the k-th arrangement in dictionary order is built one digit at a time by skipping whole blocks of arrangements, without listing any of them.
The numbers 1, 2, ..., n can be put in order in n! different ways. Write all of these arrangements as strings and sort them the way a dictionary sorts words. For n = 3 the list is "123", "132", "213", "231", "312", "321", and its entries are numbered from 1.
Given n and a position k in this list, return the arrangement at position k.
Worked Examples
n = 3, k = 3"213"n = 4, k = 9"2314"n = 3, k = 1"123"⚖️Formal Constraints & Bounds
1 <= n <= 91 <= k <= n!
Why It Works & Core Invariant
Arrangements in dictionary order come in equal blocks, one per unused digit, so the k-th one is read digit by digit: skip k // block whole blocks, keep k % block, and shrink to the next slot.
Real-World Scenario & Production Applications
Rubik's Cube solvers such as Herbert Kociemba's two-phase algorithm turn an arrangement of the cube's pieces into one number, its rank in dictionary order, and turn numbers back into arrangements, so their lookup tables can be plain arrays indexed by that number. Turning a rank back into an arrangement is exactly this problem.
Subproblems & Recurrence Decomposition3 Phases
m different digits have m! orders. With the table fact, each slot's block size is a lookup: every unused digit starts a block of fact[n - 1 - slot] arrangements.
fact = [1] * n
for m in range(1, n):
fact[m] = fact[m - 1] * mStep-by-Step Execution Trace Table
The debugger's first preset, n = 3, k = 3 (LeetCode Example 1, the trap case), with fact = [1, 1, 2] and k = 2 after k -= 1:
| Slot | block | index = k // block | k after k %= block | pool before | Digit taken | result |
|---|---|---|---|---|---|---|
| 0 | fact[2] = 2 | 2 // 2 = 1 | 0 | ['1', '2', '3'] | '2' | ['2'] |
| 1 | fact[1] = 1 | 0 // 1 = 0 | 0 | ['1', '3'] | '1' | ['2', '1'] |
| 2 | fact[0] = 1 | 0 // 1 = 0 | 0 | ['3'] | '3' | "213" |
Without k -= 1, slot 0 would still take '2' (3 // 2 = 1) but leave k = 1, and slot 1 would compute 1 // 1 = 1 and take '3': one block too far, ending at "231".
| 1 | The arrangements in dictionary order come in blocks, one per first digit, each with `(n - 1)!` arrangements: skip whole blocks instead of listing them. |
| 2 | Keep this true: after `k -= 1`, `k` is the number of arrangements that start with `result` and come before the answer. |
| 3 | The shape: a factorial table; `k -= 1`; for each slot, `block = fact[n - 1 - slot]`, `index = k // block`, `k %= block`, and `pool.pop(index)` onto the result. |
| 4 | The trap: `k` counts from 1. Without `k -= 1`, a `k` that is a multiple of `block` picks one block too far: `n = 3, k = 3` gives `"231"` instead of `"213"`. |
Target: Permutation Sequence (LeetCode 60). `fact[m]` is how many orders `m` different digits have. Building the table once keeps every block size a lookup.
Boundary pointers contract inward after each directional sweep; modular arithmetic bounds state cyclically.
while top <= bottom and left <= right: sweep right, down, left, up, contracting respective pointer.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Listing all n! arrangements to read the k-th one is hopeless for large k. But a list in dictionary order is made of blocks: every arrangement that starts with 1 comes first, then every one that starts with 2, and so on, and each block holds (n - 1)! arrangements. Count and Skip never lists anything: it asks how many whole blocks come before the answer, k // block, jumps over them, and repeats the question inside the block it landed in, one slot further right and one factorial smaller.
📚 The Analogy: Finding Page k in a Set of Volumes
An encyclopedia comes in volumes of exactly 500 pages each. To open page 1,730 you do not leaf through from page 1: 1,729 pages come before it, which is 3 whole volumes (1,500 pages) and 229 pages more, so you take volume 4 and open its page 230. Each slot of an arrangement is one more level of volumes: the first digit picks the volume, the second digit the chapter, and so on.
🪄 The Mathematical Harmony / Magic Trick
k -= 1for slot in range(n): block = fact[n - 1 - slot] index = k // block k %= block result.append(pool.pop(index)) After k -= 1, k counts the arrangements that come before the answer. The blocks at a slot come in the same order as the unused digits in pool and all have block arrangements, so exactly index = k // block of them lie before the answer, and k % block is where the answer sits inside its own block. The digits written this way, index at each slot, are the factorial number system: k in a base that is (n - 1)!, then (n - 2)!, and so on.
💡 Summary
Subtract 1 from k, then at each slot skip k // block whole blocks, keep k % block, and take that digit out of the pool. n slots, each with an O(n) pop: time and space, whatever k is.
The 1-based rank:
k -= 1before the loop:kcounts from 1, and without it everykthat is a multiple ofblockpicks one block too far:n = 3, k = 3gives"231"instead of"213".Block size:
block = fact[n - 1 - slot], notfact[n - slot]: a block holds the arrangements of the slots after this one, one factorial smaller than the number of digits still unused.Removing the used digit:
pool.pop(index), notpool[index]: the chosen digit must leave the pool, or the next slot counts it again and the answer repeats a digit.Blocks of different sizes: When the blocks at a slot have different sizes, as in Kth Smallest Instructions (LC 1643) or K-th Smallest in Lexicographical Order (LC 440), compare
kwith each choice's own count in order and subtract the counts you skip:k // blockonly works when every block at a slot is the same size.
4-Phase Thought Process Model
You will see how a senior engineer turns "the arrangement at position k" into skipping whole blocks, and says so out loud.
Pattern Recognition Signals
The 10-second spot
"All of these arrangements ... sort them the way a dictionary sorts words", "its entries are numbered from 1" and "return the arrangement at position k", with k up to n!: a rank in a sorted list far too long to build. That is the signal for Count and Skip: count how many arrangements each choice covers and jump over whole blocks.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After k -= 1, k is the number of arrangements that start with result and come before the answer. At each slot every unused digit starts a block of block = fact[n - 1 - slot] arrangements, so index = k // block blocks are skipped, pool.pop(index) is the digit, and k %= block is the rank inside that block.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
k -= 1first:kis 1-based, and without it akthat is a multiple ofblockpicks one block too far, son = 3, k = 3gives"231"instead of"213".block = fact[n - 1 - slot], notfact[n - slot]: a block holds the orders of the slots after this one.index = k // blockbeforek %= block: the modulo replacesk, so the other order always picks index 0.pool.pop(index), notpool[index]: the used digit must leave the pool, or the next slot counts it again and a digit repeats.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Count and Skip. Listing all n factorial arrangements is far too slow, but in dictionary order they come in blocks: every arrangement that starts with the same digit sits together, and each block has n minus one factorial members. First I subtract one from k, so it counts the arrangements before the answer. Then for each slot, block is the factorial of the slots still to fill after this one, k divided by block is how many whole blocks I skip, so that index into the unused digits is this slot's digit, and k mod block is the rank inside that block. I pop the digit out of the pool so it isn't used twice. The trap is the one-based k: without subtracting one, a k that's a multiple of the block size lands one block too far. That's n slots with an
O(n)pop each, so O(N squared) time andO(N)space.
So: k -= 1, k // block blocks skipped and k % block kept at each slot, the used digit popped; O(N^2) time, O(N) space.
Complexity & Mathematical Proof
O(N^2)
Count the work in getPermutation. Building fact runs N - 1 multiplications. The for slot in range(n) loop runs N times; each pass does one lookup, one division, one modulo and one pool.pop(index). The division and modulo are O(1) (all values fit below 9! = 362,880), but pop from the middle of a list shifts the digits after it, up to N - 1 of them. So each slot costs O(N), and N slots cost O(N^2). The "".join at the end is O(N). The number of steps never depends on k; only the cost of each pop does, and it is at most O(N).
O(N)
fact, pool and result each hold at most N items, plus a few integers (k, slot, block, index): O(N). There is no recursion. The returned string has N characters and is counted in the same O(N).
T(N) = (N - 1) table steps + N slots · O(N) pop = O(N^2)
Derivation Progression
N - 1
for m in range(1, n) does one multiplication per entry.
N
for slot in range(n) fixes one digit per pass.
O(N)
k // block and k %= block are O(1); pool.pop(index) shifts up to N - 1 digits.
O(N^2)
N passes of O(N) work, whatever k is.
Variable Definitions
n, the number of digits arranged (at most 9)
Memory Architecture & Bounds
O(1): one call, no recursion
O(N): fact, pool and result
O(N): the returned string of N digits
Boundary Best / Worst Cases
: for the last arrangement every index is the end of pool, so each pop is O(1)
: for the first arrangement every index is 0, and each pop(0) shifts the rest of pool
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "sort them the way a dictionary sorts words", "numbered from 1", "the arrangement at position k". A rank in a sorted list of arrangements far too long to build: Count and Skip, whole blocks of equal size skipped one slot at a time.
n <= 9, so there are at most arrangements and k fits easily in 32 bits. Generating arrangements up to the k-th costs up to steps; Count and Skip needs 9 slots.
With larger n (or multisets, as in Minimum Number of Operations to Make String Sorted (LC 1830)) the block sizes grow past 64 bits: use arbitrary-precision integers, a modulus when only a count is wanted, or cap the sizes at k when only the k-th item is wanted. Decoding many ranks against the same n can share one factorial table.
Core Algorithmic State Invariants
- Equal Blocks per Slot
Every unused digit starts a block of fact[n - 1 - slot] arrangements, and the blocks come in the order of the digits in pool. The answer's digit is decided by how many whole blocks lie before it.
- Count From 0
k -= 1 turns the 1-based position into the number of arrangements before the answer. Without it, n = 3, k = 3 takes one block too many at the second slot and returns "231".
- Divide, Keep the Rest, Remove the Digit
index = k // block, then k %= block, then pool.pop(index): N slots with an O(N) pop each, O(N^2) time and O(N) space, whatever k is.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Block sizes: m! arrangements of m digits | fact = [1] * n
for m in range(1, n):
fact[m] = fact[m - 1] * m | `fact[m]` is how many orders `m` different digits have. Building the table once keeps every block size a lookup. |
| Count from 0 (the trap) | k -= 1 | `k` is 1-based. After `k -= 1` it counts the arrangements that come before the answer, so `k // block` is the number of whole blocks to skip. |
| One block per choice at this slot | block = fact[n - 1 - slot] | Every unused digit starts a block of the orders of the digits after this slot, and all these blocks have the same size. |
| Skip whole blocks, then look inside one | index = k // block
k %= block | `index` blocks lie before the answer; `k % block` is the answer's rank inside its own block. Divide first: the modulo replaces `k`. |
| Use the digit that starts the chosen block | result.append(pool.pop(index)) | `pool` holds the unused digits in increasing order, the same order as the blocks, and `pop` removes the used one. |
| The slots, left to right | return "".join(result) | After `n` slots every digit is used and `k` is 0: the joined digits are the answer. |