AussieCoder

Posted on May 18

LeetCode Solution: 12. Integer to Roman

#leetcode #dsa #programming #tutorial

Mastering Roman Numerals: A LeetCode Journey with Integer to Roman!

Hey everyone! 👋 Aaradhya here, your guide to demystifying LeetCode problems and turning tricky challenges into fun learning experiences. Today, we're diving into a classic: LeetCode problem 12. Integer to Roman.

Ever wondered how ancient Romans managed their numbers? It's a system that looks complex at first glance, but once you break it down, it's quite elegant. And that's exactly what we'll do with this problem!

The Challenge: Integer to Roman 📜

Our mission is simple: given an integer (like 3749 or 58), we need to convert it into its Roman numeral equivalent ("MMMDCCXLIX" or "LVIII").

Here's a quick refresher on Roman numerals:

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

The key rules for forming Roman numerals are:

Highest to Lowest Place Values: You convert each decimal place value (thousands, hundreds, tens, units) and append them.
Repetition: Symbols like I, X, C, M can be repeated up to three times (e.g., III for 3, XXX for 30). You cannot repeat V, L, D.
The Subtractive Rule: This is where it gets interesting! Instead of IIII for 4, we write IV (1 less than 5). Similarly, IX for 9, XL for 40, XC for 90, CD for 400, and CM for 900. Only specific subtractive forms are allowed, always using a power of 10 (I, X, C) before a larger symbol.

Let's look at 3749 again:

3000 is MMM
700 is DCC (500 + 100 + 100)
40 is XL (10 less than 50) - subtractive form!
9 is IX (1 less than 10) - subtractive form! Result: MMMDCCXLIX

The input integer num will always be between 1 and 3999.

The Aha! Moment (Intuition) 💡

Reading all those rules might feel a bit overwhelming, right? But here's the secret: greedy approach!

Imagine you have num = 1994.

You want the biggest Roman numeral you can get out of 1994. M (1000) is the largest.
- Append M. num becomes 994.
Now, what's the biggest Roman numeral for 994? CM (900) is the largest.
- Append CM. num becomes 94.
Next for 94? XC (90) is the largest.
- Append XC. num becomes 4.
Finally for 4? IV (4) is the largest.
- Append IV. num becomes 0.

And just like that, 1994 becomes MCMXCIV!

The core idea is: always pick the largest possible Roman numeral value that is less than or equal to your current number, append its symbol, and subtract its value. Keep doing this until your number becomes zero.

Step-by-Step Approach 🚶‍♀️

Create a Lookup Table: We need a way to quickly find the Roman numeral symbols and their values. The trick is to include both the standard values (1000, 500, 100, etc.) and the special subtractive forms (900, 400, 90, 40, 9, 4) in our table. Crucially, this table must be sorted from largest value to smallest. This order is what makes the greedy approach work flawlessly.

Here's our ordered (value, symbol) list:
```
(1000, "M")
(900, "CM")  # Subtractive for 900
(500, "D")
(400, "CD")  # Subtractive for 400
(100, "C")
(90, "XC")   # Subtractive for 90
(50, "L")
(40, "XL")   # Subtractive for 40
(10, "X")
(9, "IX")    # Subtractive for 9
(5, "V")
(4, "IV")    # Subtractive for 4
(1, "I")
```
Initialize Result: Start with an empty string or list to build our Roman numeral. A list is often more efficient in Python for string concatenation.
Iterate and Subtract: Loop through our sorted value_symbols list.
- For each (value, symbol) pair:
  - While the input num is greater than or equal to the current value:
    - Append the symbol to our result.
    - Subtract value from num.
- Continue this process until num becomes 0.
Return Result: Once the loop finishes, join the characters in your result list to form the final Roman numeral string.

This approach works because by always picking the largest possible Roman numeral first, we naturally handle the place value decomposition and the subtractive rules without complex conditional logic. For example, when num is 90, iterating through the table, we'll hit (90, "XC") before (50, "L") or (10, "X"), ensuring XC is used instead of LXXXX.

The Code 💻

class Solution(object):
    def intToRoman(self, num):
        # Define the mapping of values to Roman numeral symbols,
        # ordered from largest to smallest. This is crucial for the greedy approach.
        # It includes both standard symbols and the special subtractive forms.
        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")
        ]

        roman_numeral_parts = [] # Use a list to store parts for efficient string building

        # Iterate through our predefined value-symbol pairs
        for value, symbol in value_symbols:
            # Greedily subtract the largest possible value
            # as long as num is greater than or equal to the current value
            while num >= value:
                roman_numeral_parts.append(symbol)
                num -= value

        # Join all the collected parts to form the final Roman numeral string
        return "".join(roman_numeral_parts)

Complexity Analysis ⏱️🚀

Time Complexity: O(1)
- Wait, O(1)? Yes! The number of value_symbols pairs is constant (13 in our case). The while loop for each value, symbol pair will execute at most a few times because the input num is bounded (1 to 3999).
- For num = 3999:
  - M is added 3 times. num becomes 999.
  - CM is added 1 time. num becomes 99.
  - XC is added 1 time. num becomes 9.
  - IX is added 1 time. num becomes 0.
- The total number of operations (comparisons, subtractions, appends) is bounded by a fixed small number regardless of the input num within its constraints. Hence, it's effectively constant time.
Space Complexity: O(1)
- We use a fixed-size value_symbols list (13 pairs).
- The roman_numeral_parts list will store at most a few characters (e.g., "MMMDCCXLIX" has 10 characters for 3749).
- Both are bounded by constants, so the space complexity is constant.

Key Takeaways ✨

Greedy is Your Friend: For problems involving converting numbers to specific representations, especially when there are fixed rules and ordered values, a greedy approach (always taking the largest possible chunk) can be incredibly effective.
Lookup Tables: Pre-defining mappings in a structured way (like our value_symbols list) simplifies complex conditional logic significantly.
Order Matters: The success of the greedy approach hinges on the value_symbols being sorted correctly from largest to smallest.
String Building Efficiency: In Python, appending to a list of characters and then "".join() is generally more efficient for building strings in a loop than repeated string concatenation.

Hope this breakdown helped you conquer Integer to Roman! Keep coding, keep learning, and I'll see you in the next one!

Author: aaradhyanegi009
Published: 2026-05-18 19:04:35

DEV Community