Integer to Roman

Difficulty: Medium
Topics: Hash Table, Math, String
Link: https://leetcode.com/problems/integer-to-roman/

Problem Description

Seven different symbols represent Roman numerals with the following values:

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.

Given an integer, convert it to a Roman numeral.

Example 1:

Input: num = 3749

Output: “MMMDCCXLIX”

Explanation:


3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC as 500 (D) + 100 (C) + 100 (C)
  40 = XL as 10 (X) less of 50 (L)
   9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places

Example 2:

Input: num = 58

Output: “LVIII”

Explanation:


50 = L
 8 = VIII

Example 3:

Input: num = 1994

Output: “MCMXCIV”

Explanation:


1000 = M
 900 = CM
  90 = XC
   4 = IV

Constraints:

1 <= num <= 3999

Solution

1. Problem Deconstruction

Technical Restatement
Given an integer $num$ where $1 \leq num \leq 3999$ , implement a deterministic mapping $f: \mathbb{Z} \to \Sigma^*$ where $\Sigma = \{I, V, X, L, C, D, M\}$ that satisfies:

Place Value Decomposition: $num = \sum_{i=0}^{k} d_i \cdot 10^i$ where $d_i \in [0,9]$
Symbolic Mapping: Each $d_i \cdot 10^i$ $d_{i} \cdot 1 0^{i}$ maps to a Roman numeral substring via:
- Standard Form: If $d_i \in \{1,2,3,5,6,7,8\}$ , concatenate maximal subtractable symbols (e.g., $3 \to III$ )
- Subtractive Form: If $d_i \in \{4,9\}$ , use inverted symbol pairs (e.g., $4 \to IV$ )
Concatenation Rule: Substrings are ordered from highest place value ( $10^k$ ) to lowest ( $10^0$ )

Beginner Restatement
Convert a number (like 3749) into Roman numerals by:

Breaking it into thousands, hundreds, tens, and ones
Converting each part separately:
- If a part is 4 or 9, use special combinations (like IV for 4)
- Otherwise, combine standard symbols (like VIII for 8)
Joining all parts from largest to smallest

Mathematical Restatement
Let $num = \sum_{i=0}^{3} d_i10^i$ . Define mapping $g(d,i)$ for digit $d$ at place $10^i$ :

g(d,i) = \begin{cases} \text{repeat}(S_{5i+1}, d) & \text{if } d \in [1,3] \\ S_{5i+1}S_{5i+2} & \text{if } d=4 \\ S_{5i+2}\text{repeat}(S_{5i+1}, d-5) & \text{if } d \in [5,8] \\ S_{5i+1}S_{5i+3} & \text{if } d=9 \end{cases}

Where $S = [I,V,X,L,C,D,M]$ and $repeat(s,n)$ concatenates $s$ $n$ times. Final result: $\oplus_{i=3}^0 g(d_i,i)$

Constraint Analysis

$1 \leq num \leq 3999$ $1 \leq n u m \leq 3999$ :
- Limits symbols to M (1000) as highest, maximum MMM (3000)
- No need for symbols beyond M (e.g., 5000)
- Implies 4-digit max → $O(1)$ time complexity
Hidden edge cases:
- $num = 1$ (minimum input) → “I”
- $num = 3999$ (maximum) → “MMMCMXCIX”
- All digits 4/9: 1994 → “MCMXCIV”
- All digits 1-3: 333 → “CCCXXXIII”

2. Intuition Scaffolding

Real-World Metaphor
Like making change for a dollar using fixed denominations ($100, $50, $20, etc.), but with special rules:

Can’t use four $10 bills → must use $10 + $50 combination ( $XL$ )
$9 is tricky → use $10 - $1 ( $IX$ )

Gaming Analogy
Crafting potions with limited ingredients:

Basic ingredients: I(1), V(5), X(10)…
Recipe rules:
- Max 3 of same ingredient in row
- Special combos: IV(4), IX(9) save space
- Always craft largest potions first (1000s before 100s)

Math Analogy
Greedy base-conversion with non-standard digits:

Standard base-10: 3749 = 3×1000 + 7×100 + 4×10 + 9×1
Roman “digits” are variable-length: MMM + DCC + XL + IX

Common Pitfalls

Wrong subtractive pairs: Using IL for 49 (should be XLIX)
Over-concatenation: Writing IIII for 4 (violates 3-repeat rule)
Wrong order: Writing IV for 4 but IX for 9 (must be consistent)
Place value confusion: Treating 90 as XC (correct) vs IC (wrong)
Over-engineering: Trying to handle numbers >3999 unnecessarily

3. Approach Encyclopedia

Approach 1: Direct Mapping (Optimal)

def intToRoman(num: int) -> str:
    # Define symbols for each decimal place
    thousands = ["", "M", "MM", "MMM"]
    hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
    tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
    ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
    
    return (thousands[num // 1000] + 
            hundreds[(num % 1000) // 100] + 
            tens[(num % 100) // 10] + 
            ones[num % 10])

Complexity Proof

Time: $O(1)$ $O (1)$
- Fixed 4 divisions/modulos → $4\times O(1)$
- Array lookups by index → $4\times O(1)$
- String concatenation → total length ≤15 characters
Space: $O(1)$ $O (1)$
- Predefined arrays size: $4 + 10 + 10 + 10 = 34$ elements
- Output string bounded by 3999 → max “MMMCMXCIX” (9 chars)

Visualization

3749 → [3000, 700, 40, 9]
       ↓    ↓    ↓   ↓
      MMM + DCC + XL + IX
       ↓    ↓    ↓   ↓
     "MMMDCCXLIX"

Approach 2: Greedy Subtraction

def intToRoman(num: int) -> str:
    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"]
    result = []
    
    for i in range(len(values)):
        while num >= values[i]:
            num -= values[i]
            result.append(symbols[i])
    
    return "".join(result)

Complexity Proof

Time: $O(1)$ $O (1)$
- Max iterations: 3999/1 = 3999, but only 13 symbols → constant
- Each while loop: $O(\log_{symbol} num)$ but bounded by fixed values
Space: $O(1)$ $O (1)$
- Predefined arrays size 13
- Result list ≤15 characters

4. Code Deep Dive

Optimal Solution (Direct Mapping)

def intToRoman(num: int) -> str:
    # Thousands: Handle 1000-3000 (0-3 thousands)
    thousands = ["", "M", "MM", "MMM"]  # Index 0-3 map to digit value
    # Hundreds: All combinations including subtractive (CD, CM)
    hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
    # Tens: Same pattern as hundreds but with X,L
    tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
    # Ones: Same pattern with I,V
    ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
    
    # Extract digits using integer division
    # num // 1000 = thousands digit (0-3)
    # (num % 1000) // 100 = hundreds digit (0-9)
    # (num % 100) // 10 = tens digit (0-9)  
    # num % 10 = ones digit (0-9)
    return thousands[num // 1000] + hundreds[(num % 1000) // 100] + tens[(num % 100) // 10] + ones[num % 10]

Edge Case Handling

Example 1 (3749):
- Thousands: 3749//1000=3 → “MMM”
- Hundreds: (3749%1000)=749//100=7 → “DCC”
- Tens: (3749%100)=49//10=4 → “XL”
- Ones: 3749%10=9 → “IX” → “MMMDCCXLIX” ✓
Example 2 (58):
- Thousands: 0 → “”
- Hundreds: 0 → “”
- Tens: 5 → “L”
- Ones: 8 → “VIII” → “LVIII” ✓
Example 3 (1994):
- Thousands: 1 → “M”
- Hundreds: 9 → “CM”
- Tens: 9 → “XC”
- Ones: 4 → “IV” → “MCMXCIV” ✓

5. Complexity War Room

Hardware-Aware Analysis

34-element lookup tables fit in 1-2 cache lines (64 bytes/element)
4 integer divisions: modern CPUs handle in 1-2 cycles each
Max output 9 chars → fits in stack allocation, no heap overhead

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Direct Mapping	O(1)	O(1)	10/10	✅ Best for interviews
Greedy Subtraction	O(1)	O(1)	8/10	✅ Demonstrates algorithm
Recursive Decomposition	O(1)	O(1)	6/10	❌ Overcomplicated

6. Pro Mode Extras

Variants Section

Roman to Integer (LC 13): Reverse mapping with subtractive detection
Integer to Roman (Extended): Handle numbers >3999 with Vinculum notation
Minimal Roman Form: Find shortest representation (e.g., IIII vs IV)
Roman Arithmetic: Add/Subtract Roman numerals directly

Interview Cheat Sheet

Always mention: “Since input is bounded, complexity is O(1)”
Key insight: “Roman numerals are place-value based with special 4/9 cases”
Testing strategy: Check 4/9 digits, min/max values, all-same-digit cases
Common follow-up: “How would you handle larger numbers?” (Discuss extended symbols)

#12 - Integer to Roman

Integer to Roman

Problem Description

Solution

1. Problem Deconstruction

2. Intuition Scaffolding

3. Approach Encyclopedia

4. Code Deep Dive

5. Complexity War Room

6. Pro Mode Extras