LeetCode 12 - Integer to Roman

Difficulty: 🟡 Medium
Topics: Hash Table, Math, String

Solution

Problem Understanding

The problem asks us to convert a positive integer into its Roman numeral representation. Roman numerals use combinations of specific symbols to represent values, and the rules for combining those symbols are strict. Unlike a positional number system such as decimal, Roman numerals are constructed greedily from the largest possible symbol values down to the smallest.

The input is a single integer num, where 1 <= num <= 3999. The output should be a string representing the equivalent Roman numeral.

The Roman numeral system uses these symbols:

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

Most Roman numerals are formed by repeatedly subtracting the largest possible value from the remaining number and appending the corresponding symbol. However, there are special subtractive cases. Instead of writing four identical symbols in a row, Roman numerals use compact subtractive forms:

Value	Roman
4	IV
9	IX
40	XL
90	XC
400	CD
900	CM

For example, 4 is written as IV instead of IIII, and 900 is written as CM instead of DCCCC.

The constraint limit of 3999 is important because standard Roman numerals traditionally stop there. This means the solution only needs to support symbols up to M.

Several edge cases can cause mistakes in a naive implementation. Numbers containing 4 or 9 in any decimal place require subtractive notation. For example, 49 must become XLIX, not IL. Another important case is repeated symbols. Roman numerals allow at most three consecutive repetitions of I, X, C, and M. Symbols like V, L, and D cannot repeat. The problem guarantees that the input is always valid and within range, so we do not need to handle invalid or negative numbers.

Approaches

Brute Force Approach

A brute force solution could attempt to simulate Roman numeral construction digit by digit using many conditional checks for thousands, hundreds, tens, and ones places separately. For each decimal place, the algorithm would repeatedly append symbols according to Roman numeral rules.

For example, if the number is 3749, the algorithm would process:

Thousands digit 3 → "MMM"
Hundreds digit 7 → "DCC"
Tens digit 4 → "XL"
Ones digit 9 → "IX"

This approach works because Roman numerals are fundamentally based on decimal place decomposition. However, implementing every rule manually with nested conditions becomes verbose and error-prone. It also duplicates logic across place values.

Although the runtime is still small due to the constraint limit, the implementation complexity is unnecessarily high.

Optimal Greedy Approach

The key insight is that Roman numerals can be built greedily from largest value to smallest value.

At every step, we choose the largest Roman numeral value that does not exceed the remaining number. We append its symbol to the result and subtract its value from the number. This naturally handles both standard and subtractive forms.

For example:

1994
Largest value ≤ 1994 is 1000 → append "M"
Remaining = 994
Largest value ≤ 994 is 900 → append "CM"
Remaining = 94
Largest value ≤ 94 is 90 → append "XC"
Remaining = 4
Largest value ≤ 4 is 4 → append "IV"

Result = "MCMXCIV"

This works cleanly because Roman numerals are designed around descending value composition.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1)	O(1)	Uses many manual conditional rules for each digit place
Optimal	O(1)	O(1)	Greedy construction using predefined value-symbol pairs

Even though both are technically constant time because the input range is bounded, the greedy solution is cleaner, more scalable, and easier to reason about.

Algorithm Walkthrough

Create an ordered list of Roman numeral value-symbol pairs.

The list must include both standard symbols and subtractive forms. The pairs are arranged from largest to smallest value so the algorithm can greedily consume the number.

Example:

1000 -> M
900  -> CM
500  -> D
400  -> CD
...
1    -> I

Initialize an empty result string.

This string will store the Roman numeral as we construct it. 3. Iterate through the value-symbol pairs in descending order.

For each pair, check whether the current number is greater than or equal to the value. 4. While the current value fits into the remaining number:

Append the corresponding Roman symbol to the result.
Subtract the value from the number.

This greedy process ensures we always use the largest possible Roman numeral representation first. 5. Continue until the remaining number becomes zero.

Once the number reaches zero, the Roman numeral is complete. 6. Return the constructed result string.

Why it works

The algorithm works because Roman numerals are fundamentally a greedy representation system. Every valid Roman numeral is constructed by repeatedly taking the largest possible legal symbol or subtractive pair. Since the list includes all required subtractive forms and is ordered from largest to smallest, the algorithm always produces the canonical Roman numeral representation without violating Roman numeral rules.

Python Solution

class Solution:
    def intToRoman(self, num: int) -> str:
        value_symbols = [
            (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 value_symbols:
            while num >= value:
                result.append(symbol)
                num -= value

        return "".join(result)

The implementation starts by defining the Roman numeral mappings in descending order. Including subtractive forms such as CM and IV is essential because these special cases cannot be derived automatically from the standard symbols.

The result list is used instead of repeated string concatenation because appending to a list is efficient in Python. At the end, "".join(result) constructs the final Roman numeral string.

The main loop iterates through each value-symbol pair. For every pair, the inner while loop repeatedly applies the symbol as long as the remaining number is large enough.

For example, if num = 3000, the algorithm appends "M" three times before moving to the next value.

This implementation directly follows the greedy algorithm described earlier.

Go Solution

func intToRoman(num int) string {
    valueSymbols := []struct {
        value  int
        symbol string
    }{
        {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 _, pair := range valueSymbols {
        for num >= pair.value {
            result += pair.symbol
            num -= pair.value
        }
    }

    return result
}

The Go implementation mirrors the Python logic closely. Since Go does not have tuples, the mapping is stored as a slice of anonymous structs containing value and symbol.

String concatenation is acceptable here because the Roman numeral length is very small, bounded by the problem constraints. In larger string-building problems, a strings.Builder would usually be preferred for efficiency.

Go integers easily handle values up to 3999, so overflow is not a concern.

Worked Examples

Example 1: `num = 3749`

Step	Current Value	Symbol	Remaining Number	Result
1	1000	M	2749	M
2	1000	M	1749	MM
3	1000	M	749	MMM
4	500	D	249	MMMD
5	100	C	149	MMMDC
6	100	C	49	MMMDCC
7	40	XL	9	MMMDCCXL
8	9	IX	0	MMMDCCXLIX

Final result:

MMMDCCXLIX

Example 2: `num = 58`

Step	Current Value	Symbol	Remaining Number	Result
1	50	L	8	L
2	5	V	3	LV
3	1	I	2	LVI
4	1	I	1	LVII
5	1	I	0	LVIII

Final result:

LVIII

Example 3: `num = 1994`

Step	Current Value	Symbol	Remaining Number	Result
1	1000	M	994	M
2	900	CM	94	MCM
3	90	XC	4	MCMXC
4	4	IV	0	MCMXCIV

Final result:

MCMXCIV

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	The number of Roman numeral pairs is fixed and bounded
Space	O(1)	Output size is bounded by Roman numeral length

Although the algorithm contains nested loops, the total amount of work is limited because Roman numerals for numbers up to 3999 are very short. The mapping list always contains exactly 13 entries, so the runtime does not grow with input size in practice.

The output string itself also has a bounded maximum length, making space usage constant as well.

Test Cases

solution = Solution()

assert solution.intToRoman(1) == "I"          # smallest valid input
assert solution.intToRoman(3) == "III"        # repeated symbols
assert solution.intToRoman(4) == "IV"         # subtractive notation
assert solution.intToRoman(9) == "IX"         # subtractive notation
assert solution.intToRoman(14) == "XIV"       # mixed standard and subtractive
assert solution.intToRoman(40) == "XL"        # subtractive tens
assert solution.intToRoman(58) == "LVIII"     # example case
assert solution.intToRoman(90) == "XC"        # subtractive tens
assert solution.intToRoman(400) == "CD"       # subtractive hundreds
assert solution.intToRoman(900) == "CM"       # subtractive hundreds
assert solution.intToRoman(944) == "CMXLIV"   # multiple subtractive forms
assert solution.intToRoman(1994) == "MCMXCIV" # example case
assert solution.intToRoman(3749) == "MMMDCCXLIX" # example case
assert solution.intToRoman(3999) == "MMMCMXCIX"  # largest valid input

Test	Why
`1`	Validates smallest boundary
`3`	Verifies repeated symbols
`4`	Tests subtractive notation
`9`	Tests subtractive notation
`14`	Tests mixed representation
`40`	Tests subtractive tens
`58`	Confirms provided example
`90`	Tests subtractive tens
`400`	Tests subtractive hundreds
`900`	Tests subtractive hundreds
`944`	Validates multiple subtractive forms together
`1994`	Confirms provided example
`3749`	Confirms provided example
`3999`	Validates upper boundary

Edge Cases

One important edge case is numbers containing 4 or 9 in any decimal place. Roman numerals use subtractive notation for these values, so 4 becomes IV instead of IIII, and 90 becomes XC instead of LXXXX. A naive implementation that repeatedly appends symbols without accounting for subtractive forms would generate invalid Roman numerals. This implementation handles the issue correctly by explicitly including subtractive pairs in the mapping list.

Another critical edge case is the maximum valid input, 3999. This number produces the longest standard Roman numeral: "MMMCMXCIX". Some incorrect implementations fail because they do not process symbols in descending order or forget to include 900 and 90 mappings. Since this algorithm greedily consumes values from largest to smallest, it correctly constructs the numeral without ambiguity.

A third edge case involves repeated symbols. Roman numeral rules allow at most three consecutive repetitions of I, X, C, and M. Values such as 4, 40, and 400 must therefore use subtractive notation instead of four repeated symbols. By including IV, XL, and CD directly in the lookup table, the implementation automatically avoids invalid repetitions.

A final subtle case is numbers like 49. Some incorrect solutions attempt to use non-standard subtractive forms such as IL. Roman numerals must be constructed independently by decimal place, so 49 must become XLIX. Because the greedy mapping includes only legal Roman numeral combinations, the algorithm always generates valid canonical forms.

LeetCode 12 - Integer to Roman

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Greedy Approach

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1: num = 3749

Example 2: num = 58

Example 3: num = 1994

Complexity Analysis

Test Cases

Edge Cases

Example 1: `num = 3749`

Example 2: `num = 58`

Example 3: `num = 1994`