LeetCode 12: Integer to Roman

Problem Restatement

We are given an integer num.

We need to convert it into a Roman numeral string.

Roman numerals use seven base symbols:

The input satisfies:

1 <= num <= 3999

The LeetCode statement also defines the subtractive forms:

These are the only subtractive forms used.

Input and Output

Example function shape:

def intToRoman(num: int) -> str:
    ...

Examples

Example 1:

num = 3749

Break it by place value:

3000 = MMM
700  = DCC
40   = XL
9    = IX

Output:

"MMMDCCXLIX"

Example 2:

num = 58

Break it down:

50 = L
8  = VIII

Output:

"LVIII"

Example 3:

num = 1994

Break it down:

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

Output:

"MCMXCIV"

First Thought: Convert Each Decimal Place

One valid approach is to convert thousands, hundreds, tens, and ones separately.

For example, for 1994:

1000 -> M
900  -> CM
90   -> XC
4    -> IV

This works because Roman numerals are formed from highest place value to lowest place value.

But we can write the same idea more uniformly with a value-symbol table.

Key Insight

Roman numeral construction is greedy.

At each step, choose the largest Roman value that does not exceed the remaining number.

Append its symbol.

Subtract its value.

Repeat until the number becomes zero.

The important part is to include subtractive forms in the table.

Use this table from largest to smallest:

Once the subtractive forms are included, the greedy method naturally produces correct Roman numerals.

Visual Walkthrough

Use:

num = 1994

Start with the largest value.

1000 fits once:

result = "M"
num = 994

900 fits once:

result = "MCM"
num = 94

90 fits once:

result = "MCMXC"
num = 4

4 fits once:

result = "MCMXCIV"
num = 0

Return:

"MCMXCIV"

Algorithm

1. Create a list of (value, symbol) pairs from largest to smallest.
2. Create an empty result list.
3. For each (value, symbol):
   • while num >= value:
     • append symbol
     • subtract value from num
4. Join the result list into a string.

Correctness

The value-symbol table contains every standard Roman unit needed for numbers from 1 to 3999, including all valid subtractive forms.

At each step, the algorithm appends the largest symbol whose value can still be subtracted from the remaining number.

Because Roman numerals are written from larger values to smaller values, this preserves the required order.

The subtractive forms are included before their smaller components. For example, 900 appears before 500 and 100, and 4 appears before 1. So the algorithm writes CM instead of DCCCC, and IV instead of IIII.

Each append reduces num by exactly the value represented by the appended symbol. When num reaches 0, the total value of the output string equals the original input.

Therefore the algorithm returns the correct Roman numeral.

Complexity

More generally, the algorithm uses a fixed table of 13 entries.

Implementation

class Solution:
    def intToRoman(self, num: int) -> str:
        values = [
            (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"),
        ]

        result = []

        for value, symbol in values:
            while num >= value:
                result.append(symbol)
                num -= value

        return "".join(result)

Code Explanation

The table is ordered from largest to smallest:

values = [
    (1000, "M"),
    (900, "CM"),
    ...
    (1, "I"),
]

This order is what makes the greedy method work.

For each value-symbol pair:

for value, symbol in values:

Append the symbol while it still fits:

while num >= value:
    result.append(symbol)
    num -= value

For example, if num = 3000, the loop appends "M" three times.

Finally:

return "".join(result)

This combines the pieces into the final Roman numeral.

Testing

def run_tests():
    s = Solution()

    assert s.intToRoman(3) == "III"
    assert s.intToRoman(4) == "IV"
    assert s.intToRoman(9) == "IX"
    assert s.intToRoman(58) == "LVIII"
    assert s.intToRoman(1994) == "MCMXCIV"
    assert s.intToRoman(3749) == "MMMDCCXLIX"
    assert s.intToRoman(3999) == "MMMCMXCIX"
    assert s.intToRoman(1) == "I"

    print("all tests passed")

run_tests()