Hommies

Posted on May 21

LeetCode Solution: 12. Integer to Roman

#leetcode #dsa #programming #tutorial

Unraveling the Mystery of Roman Numerals: A LeetCode Journey (Problem 12. Integer to Roman)

Hey LeetCoders and aspiring developers! 👋 Today, we're taking a trip back in time to ancient Rome... well, almost! We're tackling LeetCode problem 12: "Integer to Roman." This problem asks us to convert a standard integer into its Roman numeral representation. It sounds simple, but Roman numerals have some quirky rules that make this a fun challenge. Let's dive in!

🧐 Problem Explanation: What are Roman Numerals Anyway?

Roman numerals use a system of seven symbols, each representing a specific value:

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

The general idea is to build numbers by adding these symbols. For example:

II = 1 + 1 = 2
VI = 5 + 1 = 6
LX = 50 + 10 = 60
MCC = 1000 + 100 + 100 = 1200

But here's where it gets interesting – there are special "subtractive forms" for numbers that would otherwise require four repeated symbols or just sound clunky:

Subtractive Rule: If a smaller value symbol appears before a larger value symbol, it means subtraction.
- IV = 5 - 1 = 4 (instead of IIII)
- IX = 10 - 1 = 9 (instead of VIIII)
- XL = 50 - 10 = 40
- XC = 100 - 10 = 90
- CD = 500 - 100 = 400
- CM = 1000 - 100 = 900

Crucially, the problem states that Roman numerals are formed by converting decimal place values from highest to lowest. This means when converting 3749:

You first convert 3000 (MMM)
Then 700 (DCC)
Then 40 (XL)
Then 9 (IX)
Combining them gives MMMDCCXLIX.

You can't do things like IL for 49, because I is not a decimal place lower than L (which is in the tens place, I is in the ones place). 49 is 40 (XL) + 9 (IX). This "decimal place" rule is important for understanding the valid subtractive forms.

Our task is to take an integer num (between 1 and 3999) and return its Roman numeral string representation.

🤔 Intuition: The "Aha!" Moment

When I first look at this, my brain immediately thinks, "Okay, I need to figure out which Roman symbols make up the number." But with the additive and especially the subtractive rules, a simple if num >= value: add symbol loop might get complicated fast.

The key insight comes from the combination of the specific rules and the examples:

Fixed Symbols & Values: We have a known set of symbol-value pairs.
Greedy Approach: We want to build the Roman numeral from left to right, which means processing the largest possible values first.
Subtractive Forms are Special: CM (900) is one unit in the Roman system, not D then CCCC. Same for CD, XC, XL, IX, IV. These special forms are essentially "preferred" over their additive counterparts.

This leads to the "aha!" moment: If we create a list of all valid Roman numeral values, including the subtractive forms, and sort them from largest to smallest, we can simply go through this list and greedily subtract the largest possible value from our input number until it becomes zero.

For example, if num = 900:

If we only considered M=1000, D=500, C=100, we might try to use D (500), leaving 400. Then try C four times. This would be incorrect (DCCCC).
But if our list explicitly contains (900, 'CM'), then 900 would be matched directly, giving us CM and the correct result.

✍️ Approach: Step-by-Step Greedy Conversion

Based on our intuition, here's the plan:

Create a lookup table: We'll define a list of tuples, where each tuple contains (integer_value, roman_symbol_string). This list is critical:
- It must include all standard symbols (M, D, C, L, X, V, I).
- It must also include the special subtractive forms (CM, CD, XC, XL, IX, IV).
- Crucially, this list must be sorted in descending order of the integer values. This ensures our greedy approach always picks the largest possible Roman numeral component first.
Our list will look something like this:
[(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')]
Initialize result: Start with an empty list or string to build our Roman numeral. A list is generally more efficient for appending in Python, then we'll join it at the end.
Iterate and subtract: Loop through our value_symbols list (which is sorted largest to smallest):
- For each (value, symbol) pair:
  - Check how many times this value can fit into our current num. Let's call this count. count = num // value (integer division).
  - Append the symbol repeated count times to our result list. For example, if num is 3000 and value is 1000, count will be 3, and we'll append "MMM".
  - Update num by subtracting count * value from it. This consumes the portion of the number we just converted.
  - We can add an early break if num becomes 0, as there's nothing left to convert.
Join and return: Once the loop finishes, all parts of num will have been converted. Join the elements in our result list into a single string and return it.

Let's trace num = 1994 with this approach:

res = [], num = 1994
value_symbols list: [(1000, 'M'), (900, 'CM'), ..., (1, 'I')]

`value`	`symbol`	`num` (start)	`count = num // value`	`res.append(symbol * count)`	`num -= count * value`	`num` (end)
1000	'M'	1994	1	`res = ['M']`	`1994 - 1000`	994
900	'CM'	994	1	`res = ['M', 'CM']`	`994 - 900`	94
500	'D'	94	0	-	-	94
400	'CD'	94	0	-	-	94
100	'C'	94	0	-	-	94
90	'XC'	94	1	`res = ['M', 'CM', 'XC']`	`94 - 90`	4
50	'L'	4	0	-	-	4
40	'XL'	4	0	-	-	4
10	'X'	4	0	-	-	4
9	'IX'	4	0	-	-	4
5	'V'	4	0	-	-	4
4	'IV'	4	1	`res = ['M', 'CM', 'XC', 'IV']`	`4 - 4`	0
1	'I'	0	(break loop)	-	-	0

Finally, ''.join(res) gives us "MCMXCIV", which is the correct answer! This greedy approach, combined with a carefully constructed and ordered lookup table, handles all the Roman numeral rules elegantly.

💻 Code

class Solution:
    def intToRoman(self, num: int) -> str:
        # Define the Roman numeral values and their corresponding symbols.
        # This list is crucial: it must be sorted in descending order of values,
        # and include the special subtractive forms (like 900 for CM)
        # BEFORE their additive components (like 500 for D and 100 for C).
        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')
        ]

        # Initialize an empty list to store the Roman numeral characters.
        # Appending to a list and then joining is generally more efficient
        # than repeated string concatenation in Python.
        res = []

        # Iterate through our defined value-symbol pairs.
        for value, symbol in value_symbols:
            # If num has become 0, we've converted the entire number,
            # so we can break early.
            if num == 0:
                break

            # Calculate how many times the current 'value' fits into 'num'.
            # E.g., if num = 3000 and value = 1000, count = 3.
            count = num // value

            # Append the 'symbol' repeated 'count' times to our result list.
            # E.g., if count = 3 and symbol = 'M', it appends 'MMM'.
            res.append(symbol * count)

            # Subtract the converted portion from num.
            # E.g., num = 3000 - (3 * 1000) = 0.
            num -= count * value

        # Join all the symbols in the list to form the final Roman numeral string.
        return ''.join(res)

⏱️ Time & Space Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity: O(1)
- The value_symbols list has a fixed size (13 elements).
- We iterate through this list exactly once.
- Inside the loop, operations like integer division (//), multiplication (*), list append(), and subtraction (-) take constant time. The string multiplication symbol * count and append are also bounded because the maximum count is small (at most 3 for 'I', 'X', 'C', 'M') and the Roman numeral string's total length for num <= 3999 is very short (e.g., "MMMCMXCIX" for 3999 has 7 characters).
- Since the number of iterations and the work done in each iteration are bounded by a constant (independent of the input num's magnitude, within the given constraints), the overall time complexity is constant.
Space Complexity: O(1)
- The value_symbols list is a fixed-size data structure (13 tuples), so it takes constant space.
- The res list stores the characters of the resulting Roman numeral string. The maximum length of a Roman numeral for an integer up to 3999 is also very small (e.g., "MMMCMXCIX" has 7 characters).
- Therefore, the space used is bounded by a constant, leading to O(1) space complexity.

This solution is incredibly efficient because it leverages the fixed and relatively small nature of the Roman numeral system's rules and symbols.

🎯 Key Takeaways

Greedy Approach Power: This problem is a classic example where a greedy approach shines. By always taking the largest possible valid Roman numeral component first, and ensuring your lookup table accounts for special cases (like subtractive forms) in the correct order, you can simplify complex rules.
Lookup Tables are Your Friend: When dealing with predefined mappings or rules, a well-structured lookup table (like our value_symbols list) can make your code much cleaner and easier to reason about than a series of nested if/else statements.
Order Matters! For greedy algorithms, the order of elements in your lookup table is paramount. Always ensure the largest values (including special combinations) come first.
Python String Efficiency: Appending to a list and then using ''.join() is generally more efficient for building strings than repeated string concatenation (+=) in Python, especially for potentially longer strings (though in this specific problem, the string length is so small that the difference would be negligible).

And there you have it! Converting integers to Roman numerals might seem tricky at first, but with a solid understanding of the rules and a well-designed greedy approach, it becomes quite straightforward.

Happy coding!

Author Account: p1Hzd8mRM8
Publishing Time: 2026-05-21 17:05:20

DEV Community