Integer to Roman
Problem
Given an integer num, convert it to a Roman numeral string representing the same value.
- 1 ≤ num ≤ 3999
Example
num = 1994"MCMXCIV"The algorithm decomposes 1994 by greedily subtracting the largest Roman numeral values possible. It starts with 1000 (M), subtracts it once leaving 994. Then it subtracts 900 (CM), leaving 94. Next, it subtracts 90 (XC), leaving 4. Finally, it subtracts 4 (IV). Concatenating these symbols in order yields "MCMXCIV".
Approach
Straightforward Solution
One might attempt to build the numeral by checking each symbol and subtracting it once if possible, but this would require complex conditional logic and multiple passes, making the code verbose and error-prone.
Core Observation
Roman numerals are constructed by concatenating symbols from largest to smallest values, using subtractive pairs for specific numbers. This structure allows a greedy approach where the largest possible symbol is repeatedly used until the number is reduced to zero.
Path to Optimal
PreviewThe key insight is to predefine a list of Roman numeral symbols paired with their integer values, ordered from largest to smallest, including subtractive pairs…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a predefined ordered list of (value, symbol) pairs representing all Roman numeral building blocks, including subtractive forms…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(1)
The algorithm iterates over a fixed list of 13 Roman numeral pairs regardless of input size, performing a constant number of operations.
Space
O(1)
The output string length is bounded by the maximum Roman numeral length for 3999, and the auxiliary space for the symbol list is fixed and independent of input.
Pattern Spotlight
Greedy Algorithms (Greedy Decomposition)
When converting numbers to a representation with hierarchical symbols, a greedy approach that repeatedly subtracts the largest valid symbol ensures correctness and simplicity, as Roman numerals are designed to be constructed from largest to smallest symbols.
Solution
| 1 | class Solution: |
| 2 | def intToRoman(self, num: int) -> str: |
| 3 | roman_pairs = [ |
| 4 | (1000, "M"), |
| 5 | (900, "CM"), |
| 6 | (500, "D"), |
| 7 | (400, "CD"), |
| 8 | (100, "C"), |
| 9 | (90, "XC"), |
| 10 | (50, "L"), |
| 11 | (40, "XL"), |
| 12 | (10, "X"), |
| 13 | (9, "IX"), |
| 14 | (5, "V"), |
| 15 | (4, "IV"), |
| 16 | (1, "I"), |
| 17 | ] |
| 18 | |
| 19 | roman_parts = [] |
| 20 | |
| 21 | for value, symbol in roman_pairs: |
| 22 | count = num // value |
| 23 | |
| 24 | if count > 0: |
| 25 | roman_parts.append(symbol * count) |
| 26 | num -= value * count |
| 27 | |
| 28 | return "".join(roman_parts) |
Step-by-Step Solution
Define Ordered Roman Numeral Symbol-Value Pairs Including Subtractive Notation
| 3 | roman_pairs = [ |
| 4 | (1000, "M"), |
| 5 | (900, "CM"), |
| 6 | (500, "D"), |
| 7 | (400, "CD"), |
| 8 | (100, "C"), |
| 9 | (90, "XC"), |
| 10 | (50, "L"), |
| 11 | (40, "XL"), |
| 12 | (10, "X"), |
| 13 | (9, "IX"), |
| 14 | (5, "V"), |
| 15 | (4, "IV"), |
| 16 | (1, "I"), |
| 17 | ] |
Objective
To establish a fixed ordered list of Roman numeral symbols paired with their integer values, including subtractive pairs, to enable greedy decomposition.
Key Insight
Roman numerals use specific subtractive pairs (e.g., 900 as CM, 4 as IV) that must be handled explicitly to produce valid numerals. By including these pairs in descending order alongside standard symbols, the algorithm can uniformly apply a greedy subtraction without special cases.
Interview Quick-Check
Core Logic
The ordered list includes both standard and subtractive Roman numeral pairs, enabling a single pass greedy approach.
Common Pitfalls & Bugs
Omitting subtractive pairs leads to invalid or non-minimal Roman numerals.
Accumulate Roman Numeral Symbols by Greedy Division and Subtraction
To iteratively build the Roman numeral string by subtracting the largest possible symbol values from the number and appending corresponding symbols.
Return the Concatenated Roman Numeral String
To produce the final Roman numeral string by joining all accumulated symbol parts.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 8 Critical lines interviewers watch for.
(900, "CM"),Add the subtractive pair (900, 'CM') to the list.
Including subtractive pairs like 900 (CM) is essential to produce valid Roman numerals and avoid invalid repetitions.
(400, "CD"),Add the subtractive pair (400, 'CD') to the list.
Subtractive notation for 400 ensures minimal and valid Roman numeral representation.
(90, "XC"),Add the subtractive pair (90, 'XC') to the list.
Subtractive notation for 90 is required for valid numeral formation.
Full line-by-line criticality + rationale for all 22 lines available on Pro.
Test Your Understanding
Why does greedily subtracting the largest Roman numeral values first guarantee a correct Roman numeral representation?
See the answer with Pro.
Related Problems
Greedy Algorithms pattern
Don't just read it. Drill it.
Reconstruct Integer to Roman from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Integer to Roman drill