Integer to Roman (LeetCode 12)
Roman numerals rest on seven letters, each pinned to a fixed value:
| Symbol | Value |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
Build the numeral one decimal place at a time (thousands, then hundreds, then tens, then ones), stacking each place's encoding onto the result. Two encoding rules govern each place:
- Normal case: keep peeling off the largest symbol value that still fits, appending it and shrinking the remainder, until nothing is left for that place.
- Subtractive shortcut: whenever a place's digit is 4 or 9, write it as one smaller symbol placed directly before the next larger one instead of repeating a symbol awkwardly -- so 4 becomes IV (one before five) and 9 becomes IX (one before ten). The full set of shortcuts is 4 -> IV, 9 -> IX, 40 -> XL, 90 -> XC, 400 -> CD, 900 -> CM.
- Only the "power of ten" symbols (I, X, C, M) may ever repeat, and never more than three times back to back; V, L, and D never repeat -- a fourth copy always means switching to the subtractive shortcut instead.
Your job: take an integer and produce its Roman numeral string.
Worked Examples
num = 3749"MMMDCCXLIX"num = 58"LVIII"num = 1994"MCMXCIV"⚖️Formal Constraints & Bounds
1 <= num <= 3999
Core Insight
Encode every subtractive rule (4, 9, 40, 90, 400, 900) directly as first-class entries in an ordered value/symbol table, so the runtime logic becomes a single uniform greedy loop with zero per-digit special-casing.
Real-World Scenario & Production Applications
Legacy document/edition numbering systems, clock-face and monument inscriptions, and any format that still requires canonical Roman numeral rendering.
Subproblems & Recurrence Decomposition3 Phases
Build a strictly decreasing table of (value, symbol) pairs that already encodes every subtractive-notation rule (900=CM, 400=CD, 90=XC, 40=XL, 9=IX, 4=IV) as first-class entries, not special cases.
values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]Step-by-Step Execution Trace Table
| Denomination Value | Roman Symbol | Times Divisible (num // v) | Subtracted Value (qty * v) | Remaining num | Appended Roman String |
|---|---|---|---|---|---|
| 1000 | M | 1994 // 1000 = 1 | 1000 | 994 | "M" |
| 900 | CM | 994 // 900 = 1 | 900 | 94 | "MCM" |
| 90 | XC | 94 // 90 = 1 | 90 | 4 | "MCMXC" |
| 4 | IV | 4 // 4 = 1 | 4 | 0 | "MCMXCIV" |
| 1 | values, symbols = [1000, 900, ...], ["M", "CM", ...] |
| 2 | for v, s in zip(values, symbols): |
| 3 | count = num // v |
| 4 | if count: |
| 5 | res.append(s * count) |
| 6 | num -= v * count |
| 7 | return "".join(res) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Converting a number to Roman numerals looks like it needs special-case logic for every awkward subtractive pattern (4, 9, 40, 90, 400, 900) — but a single greedy walk over a carefully ordered lookup table handles every case uniformly.
The Analogy: Making Change With a Cash Drawer
Imagine a cash drawer stocked with specially minted "bills" of value 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, and 1 (the 900/400/90/40/9/4 "bills" are the subtractive-notation trick in disguise). To make change for any amount, a cashier doesn't think about special cases — they just always hand over the biggest bill that still fits, again and again, until the drawer amount reaches zero. Because the bill values already encode the subtractive rules (a "900" bill just is CM), the greedy hand-over produces valid Roman numeral notation automatically.
🔑 The Key Idea in the Code
Because values is strictly decreasing and includes the subtractive pairs (900, 400, 90, 40, 9, 4) as first-class entries, the greedy num // v step never needs to special-case "is this a 4-like or 9-like digit?" — the table already answers that question.
Missing subtractive combination pairs in lookup table: Roman numerals use subtractive notation for 4 (
IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD), and 900 (CM). Omitting these 6 entries forces complex conditional branching.Descending order requirement: The lookup table must be iterated strictly in descending order of value (1000 down to 1). Ascending iteration greedily chooses
'I'for everything.Building strings via repeated concatenation: In languages without string builders, repeated string concatenation in loops causes copying; collect symbol tokens in a list and call
''.join().
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Convert an integer (1 to 3999) into a Roman numeral string, including subtractive forms (4, 9, 40, 90, 400, 900).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: encoding the subtractive pairs (900=CM, 400=CD, 90=XC, 40=XL, 9=IX, 4=IV) as first-class table entries removes any need for per-digit special-casing.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Hand-writing separate branches for each subtractive case instead of putting them directly in the ordered table.
Forgetting the table must be strictly decreasing by value or the greedy walk breaks.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I build a strictly decreasing table of (value, symbol) pairs that already bakes in the subtractive forms as entries. I walk the table top to bottom; at each entry I take as many copies as fit (num // v), append that many symbols, and subtract their total value from num. The loop stops once num reaches 0. This runs in
O(1)time since the table has a fixed 13 entries."
Complexity & Mathematical Proof
O(1)
Look at the loop bound: the value/symbol table has a fixed 13 entries regardless of input size, and num <= 3999 means the loop body executes at most a small constant number of times across all entries. Strict O(1) time.
O(1) Auxiliary
Look at memory allocations: the values and symbols tables are fixed-size constants (13 entries each). The output string is bounded by a constant maximum length (15 characters for num = 3888). O(1) auxiliary space.
T(N) = O(1) since the table has a fixed 13 entries
Derivation Progression
13 table entries, constant work per entry
Every entry does O(1) division and string append work.
O(1) bounded by fixed table size
Runtime never depends on the magnitude of num beyond its fixed 4-digit constraint.
Variable Definitions
Input integer, 1 <= num <= 3999
Memory Architecture & Bounds
O(1) Iterative
O(1) Fixed-size lookup tables
O(1) Bounded-length output string
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Keyword trigger: "convert an integer to a Roman numeral". The structural requirement is mapping numbers to additive and subtractive Roman literals. A Senior SWE avoids complex conditional branching trees by framing this as a Greedy Value/Symbol Table Walk.
. Domain size is strictly finite. Time and space complexities are strictly .
There are exactly 13 unique symbol pairs in total.
Integer to Roman (LeetCode 12)
Roman numerals rest on seven letters, each pinned to a fixed value:
| Symbol | Value |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
Build the numeral one decimal place at a time (thousands, then hundreds, then tens, then ones), stacking each place's encoding onto the result. Two encoding rules govern each place:
- Normal case: keep peeling off the largest symbol value that still fits, appending it and shrinking the remainder, until nothing is left for that place.
- Subtractive shortcut: whenever a place's digit is 4 or 9, write it as one smaller symbol placed directly before the next larger one instead of repeating a symbol awkwardly -- so 4 becomes IV (one before five) and 9 becomes IX (one before ten). The full set of shortcuts is 4 -> IV, 9 -> IX, 40 -> XL, 90 -> XC, 400 -> CD, 900 -> CM.
- Only the "power of ten" symbols (I, X, C, M) may ever repeat, and never more than three times back to back; V, L, and D never repeat -- a fourth copy always means switching to the subtractive shortcut instead.
Your job: take an integer and produce its Roman numeral string.
Worked Examples
num = 3749"MMMDCCXLIX"num = 58"LVIII"num = 1994"MCMXCIV"⚖️Formal Constraints & Bounds
1 <= num <= 3999
Core Insight
Encode every subtractive rule (4, 9, 40, 90, 400, 900) directly as first-class entries in an ordered value/symbol table, so the runtime logic becomes a single uniform greedy loop with zero per-digit special-casing.
Real-World Scenario & Production Applications
Legacy document/edition numbering systems, clock-face and monument inscriptions, and any format that still requires canonical Roman numeral rendering.
Subproblems & Recurrence Decomposition3 Phases
Build a strictly decreasing table of (value, symbol) pairs that already encodes every subtractive-notation rule (900=CM, 400=CD, 90=XC, 40=XL, 9=IX, 4=IV) as first-class entries, not special cases.
values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]Step-by-Step Execution Trace Table
| Denomination Value | Roman Symbol | Times Divisible (num // v) | Subtracted Value (qty * v) | Remaining num | Appended Roman String |
|---|---|---|---|---|---|
| 1000 | M | 1994 // 1000 = 1 | 1000 | 994 | "M" |
| 900 | CM | 994 // 900 = 1 | 900 | 94 | "MCM" |
| 90 | XC | 94 // 90 = 1 | 90 | 4 | "MCMXC" |
| 4 | IV | 4 // 4 = 1 | 4 | 0 | "MCMXCIV" |
| 1 | values, symbols = [1000, 900, ...], ["M", "CM", ...] |
| 2 | for v, s in zip(values, symbols): |
| 3 | count = num // v |
| 4 | if count: |
| 5 | res.append(s * count) |
| 6 | num -= v * count |
| 7 | return "".join(res) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Converting a number to Roman numerals looks like it needs special-case logic for every awkward subtractive pattern (4, 9, 40, 90, 400, 900) — but a single greedy walk over a carefully ordered lookup table handles every case uniformly.
The Analogy: Making Change With a Cash Drawer
Imagine a cash drawer stocked with specially minted "bills" of value 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, and 1 (the 900/400/90/40/9/4 "bills" are the subtractive-notation trick in disguise). To make change for any amount, a cashier doesn't think about special cases — they just always hand over the biggest bill that still fits, again and again, until the drawer amount reaches zero. Because the bill values already encode the subtractive rules (a "900" bill just is CM), the greedy hand-over produces valid Roman numeral notation automatically.
🔑 The Key Idea in the Code
Because values is strictly decreasing and includes the subtractive pairs (900, 400, 90, 40, 9, 4) as first-class entries, the greedy num // v step never needs to special-case "is this a 4-like or 9-like digit?" — the table already answers that question.
Missing subtractive combination pairs in lookup table: Roman numerals use subtractive notation for 4 (
IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD), and 900 (CM). Omitting these 6 entries forces complex conditional branching.Descending order requirement: The lookup table must be iterated strictly in descending order of value (1000 down to 1). Ascending iteration greedily chooses
'I'for everything.Building strings via repeated concatenation: In languages without string builders, repeated string concatenation in loops causes copying; collect symbol tokens in a list and call
''.join().
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Convert an integer (1 to 3999) into a Roman numeral string, including subtractive forms (4, 9, 40, 90, 400, 900).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: encoding the subtractive pairs (900=CM, 400=CD, 90=XC, 40=XL, 9=IX, 4=IV) as first-class table entries removes any need for per-digit special-casing.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Hand-writing separate branches for each subtractive case instead of putting them directly in the ordered table.
Forgetting the table must be strictly decreasing by value or the greedy walk breaks.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I build a strictly decreasing table of (value, symbol) pairs that already bakes in the subtractive forms as entries. I walk the table top to bottom; at each entry I take as many copies as fit (num // v), append that many symbols, and subtract their total value from num. The loop stops once num reaches 0. This runs in
O(1)time since the table has a fixed 13 entries."
Complexity & Mathematical Proof
O(1)
Look at the loop bound: the value/symbol table has a fixed 13 entries regardless of input size, and num <= 3999 means the loop body executes at most a small constant number of times across all entries. Strict O(1) time.
O(1) Auxiliary
Look at memory allocations: the values and symbols tables are fixed-size constants (13 entries each). The output string is bounded by a constant maximum length (15 characters for num = 3888). O(1) auxiliary space.
T(N) = O(1) since the table has a fixed 13 entries
Derivation Progression
13 table entries, constant work per entry
Every entry does O(1) division and string append work.
O(1) bounded by fixed table size
Runtime never depends on the magnitude of num beyond its fixed 4-digit constraint.
Variable Definitions
Input integer, 1 <= num <= 3999
Memory Architecture & Bounds
O(1) Iterative
O(1) Fixed-size lookup tables
O(1) Bounded-length output string
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Keyword trigger: "convert an integer to a Roman numeral". The structural requirement is mapping numbers to additive and subtractive Roman literals. A Senior SWE avoids complex conditional branching trees by framing this as a Greedy Value/Symbol Table Walk.
. Domain size is strictly finite. Time and space complexities are strictly .
There are exactly 13 unique symbol pairs in total.