LeetCode 12: Integer to Roman

Problem Statement

Given an integer num between 1 and 3999, convert it to a Roman numeral string. Roman numerals use seven symbols: I (1), V (5), X (10), L (50), C (100), D (500), and M (1000), with rules for subtractive notation (e.g., IV for 4).

Constraints

  • 1 <= num <= 3999

Example

Input: num = 3
Output: "III"
Explanation: 3 is three I’s.

Input: num = 58
Output: "LVIII"
Explanation: 50 (L) + 8 (5 + 3 = V + III) = LVIII.

Input: num = 1994
Output: "MCMXCIV"
Explanation: 1000 (M) + 900 (CM) + 90 (XC) + 4 (IV) = MCMXCIV.

Understanding the Problem

We need to turn a number like 1994 into a Roman numeral like "MCMXCIV". Roman numerals build from largest to smallest values, using subtraction for certain pairs (e.g., IV = 5 - 1 = 4). We’ll use a greedy approach, matching the largest possible Roman values step by step.

Solution: Greedy Approach

Explanation

List Roman numeral values and their symbols from largest to smallest. Repeatedly subtract the largest possible value from the number, appending its symbol, until the number becomes 0.

  1. Define Roman numeral values and symbols in descending order, including subtractive pairs.

  2. Start with an empty result string.

  3. For each value-symbol pair, while the number is at least that value, subtract it and add the symbol.

  4. Return the final string.

Step-by-Step Example

Example 1: num = 58

We have 58 and want "LVIII".

  • Goal: Convert 58 to Roman numerals.
  • Result for reference: "LVIII" (50 + 5 + 3).
  • Start: Result string is empty, num is 58.
  • Step 1: Check 1000 (M).
    • 58 < 1000, skip.
  • Step 2: Check 900 (CM).
    • 58 < 900, skip.
  • Step 3: Check 500 (D).
    • 58 < 500, skip.
  • Step 4: Check 100 (C).
    • 58 < 100, skip.
  • Step 5: Check 50 (L).
    • 58 ≥ 50, subtract 50, num = 8, add "L".
    • Result: "L".
  • Step 6: Check 10 (X).
    • 8 < 10, skip.
  • Step 7: Check 9 (IX).
    • 8 < 9, skip.
  • Step 8: Check 5 (V).
    • 8 ≥ 5, subtract 5, num = 3, add "V".
    • Result: "LV".
  • Step 9: Check 4 (IV).
    • 3 < 4, skip.
  • Step 10: Check 1 (I).
    • 3 ≥ 1, subtract 1, num = 2, add "I".
    • Result: "LVI".
    • 2 ≥ 1, subtract 1, num = 1, add "I".
    • Result: "LVII".
    • 1 ≥ 1, subtract 1, num = 0, add "I".
    • Result: "LVIII".
  • Step 11: Num is 0, stop.
  • Finish: Return "LVIII".
    • Matches 50 + 5 + 3.

Example 2: num = 1994

Now, num is 1994.

  • Goal: Convert 1994 to Roman numerals.
  • Result for reference: "MCMXCIV" (1000 + 900 + 90 + 4).
  • Start: Result empty, num = 1994.
  • Step 1: 1000 (M).
    • 1994 ≥ 1000, num = 994, add "M".
    • Result: "M".
  • Step 2: 900 (CM).
    • 994 ≥ 900, num = 94, add "CM".
    • Result: "MCM".
  • Step 3: 100 (C).
    • 94 < 100, skip.
  • Step 4: 90 (XC).
    • 94 ≥ 90, num = 4, add "XC".
    • Result: "MCMXC".
  • Step 5: 10 (X).
    • 4 < 10, skip.
  • Step 6: 9 (IX).
    • 4 < 9, skip.
  • Step 7: 5 (V).
    • 4 < 5, skip.
  • Step 8: 4 (IV).
    • 4 ≥ 4, num = 0, add "IV".
    • Result: "MCMXCIV".
  • Step 9: Num is 0, stop.
  • Finish: Return "MCMXCIV".
    • Matches 1000 + 900 + 90 + 4.

Code

Here’s the Python code to solve LeetCode 12. It’s simple and works in Python 3.6+. Try it on Replit!

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]:
            result += symbols[i]
            num -= values[i]

    return result

Note: Learn more about Python’s lists in the official docs.

Complexity

  • Time Complexity: O(1) – Fixed set of 13 values, and num is bounded by 3999.
  • Space Complexity: O(1) – Result string is small and fixed-size arrays.

Efficiency Notes

This greedy method is fast and straightforward, always picking the largest possible Roman numeral, making it ideal for LeetCode 12.

Key Insights

Tips to master LeetCode 12:

  • Know the Pairs: Memorize subtractive pairs (IV, IX, XL, etc.)—they’re key to Roman numerals.
  • Go Big First: Start with the largest values to keep the result concise.
  • Loop Smart: The while loop ensures repeated symbols (e.g., III) are handled easily.

These tips simplify the conversion!

Alternative: Hardcoded Mapping (Brief Mention)

You could use a series of if-else statements for each digit place (thousands, hundreds, etc.), but it’s less elegant and more verbose than the greedy list approach.

Additional Example

For num = 94:

  • Goal: Convert to Roman.
  • Reference: "XCIV" (90 + 4).
  • Steps: 90 (XC), 4 (IV).
  • Result: "XCIV".

Edge Cases

  • Minimum: num = 1 – Returns "I".
  • Maximum: num = 3999 – Returns "MMMCMXCIX".
  • Single Digit: num = 9 – Returns "IX".

Final Thoughts

The greedy approach is a clean, efficient way to solve LeetCode 12: Integer to Roman in Python. It’s perfect for interviews and teaches number-to-string conversion. Check out LeetCode 7: Reverse Integer for more number fun.