LeetCode #12 Medium

Integer to Roman

Convert an integer to its Roman numeral representation.

stringmathgreedy
Open on LeetCode ↗
02

Intuition

💡

The obvious plan is to greedily subtract the standard symbol values (M, D, C, L, X, V, I) and then bolt on special-case if-statements for the six subtractive forms - 4, 9, 40, 90, 400, 900 - after the fact. That works but doubles the code and is easy to get subtly wrong. Instead, put those subtractive pairs directly into the value table itself, as first-class entries ordered right alongside the plain ones, all sorted descending by value. Once CM=900 and IX=9 live in the same table as M=1000 and X=10, one greedy loop - repeatedly subtracting the largest value that still fits - handles every case uniformly, with zero special-casing.

03

Approach

1

Build one descending table

Create a list of (value, symbol) pairs covering all thirteen cases: 1000/M, 900/CM, 500/D, 400/CD, 100/C, 90/XC, 50/L, 40/XL, 10/X, 9/IX, 5/V, 4/IV, 1/I - in that exact descending order. The subtractive entries are not an afterthought; they are ordinary rows in the table.

2

Greedily consume the table

Walk the table from largest to smallest value. For each entry, while the remaining number is still at least that value, subtract it and append the symbol to the result, repeating until it no longer fits, then move to the next entry.

3

Stop once the number hits zero

Because the table is exhaustive and covers every digit position including its subtractive form, the number reaches exactly zero by the time the loop finishes, and the accumulated string is the complete Roman numeral.

04

Solution & live demo

python
1class Solution:
2 def intToRoman(self, num: int) -> str:
3 table = [(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'),
4 (100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'),
5 (10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')]
6 result = []
7 for value, symbol in table:
8 while num >= value:
9 num -= value
10 result.append(symbol)
11 return ''.join(result)
05

Edge cases

num == 4 or 9 (single digit subtractive)

Matched directly by the IV or IX table entry, no special-case code needed.

num == 3999 (maximum value)

Greedily consumes M three times, then CM, XC, IX in sequence: MMMCMXCIX.

num == 1 (minimum value)

Matches the last table entry, I, directly.

num with repeated same-value digit, e.g. 3000

The while loop inside one table entry fires three times in a row, appending MMM.

06

Complexity

Time
O(1)
Space
O(1)
The table has a fixed 13 entries and the result length is bounded by a small constant regardless of input size.