Integer to Roman: Greedy Value Decomposition

LeetCode 12, Integer to Roman, asks you to convert an integer into its roman numeral representation. The input is between 1 and 3999. Roman numerals use seven base symbols (I, V, X, L, C, D, M) plus six subtractive forms (IV, IX, XL, XC, CD, CM) to represent values without a zero or place-value system. The trick is recognizing that this conversion is a greedy decomposition problem, not a digit-by-digit mapping exercise.

Example: 1994 becomes "MCMXCIV". That breaks down as M (1000) + CM (900) + XC (90) + IV (4).

The visual above shows how the integer 1994 splits into exactly four roman numeral components. Each block represents one greedy subtraction from the remaining value. The algorithm always picks the largest value that fits.

The key insight: greedy decomposition with a lookup table

Roman numerals follow a greedy structure. The largest valid symbol always comes first. You never need to look ahead or backtrack. This means you can solve the problem by building a table of all 13 roman numeral values (the 7 base symbols plus the 6 subtractive forms), sorting them from largest to smallest, and repeatedly subtracting the largest value that still fits.

Here is the complete lookup table:

By including the subtractive forms directly in the table, you avoid needing any special-case logic. The greedy algorithm handles everything uniformly.

The solution

def int_to_roman(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)

Here is what each part does:

• Build the lookup table. Define all 13 value-symbol pairs in descending order. The subtractive forms (CM, CD, XC, XL, IX, IV) sit right between their neighbors so the greedy logic picks them up naturally.
• Iterate from largest to smallest. For each pair, use a while loop to subtract that value as many times as it fits. For example, 3000 would subtract M three times.
• Append symbols. Each time you subtract a value, append the corresponding symbol to the result list.
• Join and return. Once the number reaches zero, join all the accumulated symbols into a single string.

The while loop inside the for loop might look like it could run many iterations, but the input is bounded at 3999. The maximum number of symbols in any result is 15 (for 3888, which is MMMDCCCLXXXVIII). The total work is constant regardless of the input.

Step-by-step walkthrough

Let's trace through num = 1994 to see the greedy subtraction in action.

Notice how each step picks the largest value that fits the remaining number. After subtracting 1000, the remainder is 994. The next value that fits is 900 (CM), not 500 (D). After subtracting 900, the remainder is 94. The next value that fits is 90 (XC). Finally, 4 matches IV exactly. Four subtractions, zero remaining, done.

This is the greedy property at work. At every step, the locally optimal choice (subtract the largest possible value) leads to the globally correct answer. Roman numerals are designed so that this greedy approach always produces a valid result.

Complexity

Both time and space are constant because the problem constrains the input to a fixed range. There is no variable-size input to scale with.

The building blocks

This problem is built from two reusable building blocks.

Greedy decomposition

The technique of repeatedly selecting the largest available unit that fits. You start with the full amount, subtract the biggest piece, and continue until nothing remains. The template:

for value in sorted_values_descending:
    while amount >= value:
        use(value)
        amount -= value

This same greedy decomposition pattern appears in:

• Coin Change (greedy variant): when denominations are canonical, the greedy approach works the same way
• Jump Game: greedily extend the farthest reachable position
• Task Scheduler: greedily schedule the most frequent task first

Value lookup table

The technique of precomputing all meaningful values (including edge cases) into a flat table so that your algorithm can iterate without branching. Instead of writing if statements for subtractive forms, you encode them directly in the data.

This is a general design principle: push complexity into data, not logic. A clean lookup table makes the algorithm simpler and less error-prone.

Edge cases to watch for

• Smallest input (1). Returns "I". The loop subtracts 1 once and terminates.
• Largest input (3999). Returns "MMMCMXCIX". The loop subtracts M three times, then CM, then XC, then IX. This is the upper bound of the problem.
• Exact matches (1000). Returns "M". A single subtraction with no remainder.
• Repeated symbols (3). Returns "III". The while loop on value 1 runs three times.
• All subtractive forms (1994). A good test case because it exercises CM, XC, and IV all in one number.

From understanding to recall

The greedy decomposition of Integer to Roman is easy to understand once you see it. The challenge is recalling it under pressure. Three weeks from now, when you encounter a problem that requires greedy value subtraction, you want the "build a sorted lookup table and subtract from largest to smallest" pattern to surface automatically.

The lookup table is the part most people forget. They remember the general idea of greedy subtraction but stumble when they need to handle the six subtractive forms. Drilling the full 13-entry table until you can write it from memory eliminates that stumbling block.

Spaced repetition locks this in. You practice typing the solution from scratch at increasing intervals. After a few cycles, the lookup table and the nested loop structure become automatic. The pattern transfers to any problem where greedy decomposition from a fixed set of values is the right approach.

Related posts

• Ransom Note - Another problem where a lookup structure (frequency map) drives the entire solution, showing how precomputed data simplifies algorithm logic
• Valid Anagram - Uses the frequency counter building block, another example of encoding the problem into a data structure and iterating over it