How to Conquer Roman Numerals: LeetCode #13 Explained Simply!

Hey there, future coding superstar! 👋 Ever looked at Roman numerals and thought, "That's a cool system, but how would I code that conversion?" Today, we're diving into LeetCode problem #13, "Roman to Integer," a fantastic problem for beginners that teaches some core programming concepts.

Let's unravel this ancient number system together and turn it into elegant Python code!

The Roman Numeral Mystery (Problem Explanation)

Roman numerals use a set of seven symbols:

• I = 1
• V = 5
• X = 10
• L = 50
• C = 100
• D = 500
• M = 1000

Usually, they're written from largest value to smallest, and you just add them up. For example:

• II = 1 + 1 = 2
• XII = 10 + 1 + 1 = 12
• XXVII = 10 + 10 + 5 + 1 + 1 = 27

Sounds simple, right? But here's the twist! There are six special cases where a smaller numeral comes before a larger one, and instead of adding, you subtract it.

• IV = 4 (5 - 1)
• IX = 9 (10 - 1)
• XL = 40 (50 - 10)
• XC = 90 (100 - 10)
• CD = 400 (500 - 100)
• CM = 900 (1000 - 100)

So, your task is to take a Roman numeral string (like "MCMXCIV") and convert it into its integer equivalent (like 1994). The input string is guaranteed to be a valid Roman numeral within a certain range.

Let's look at an example to clarify:
Input: s = "MCMXCIV"
Output: 1994

• M = 1000
• CM = 900 (C before M means 1000 - 100)
• XC = 90 (X before C means 100 - 10)
• IV = 4 (I before V means 5 - 1) Total: 1000 + 900 + 90 + 4 = 1994

The "Aha!" Moment (Intuition)

The core challenge is handling those subtraction cases (IV, IX, etc.). How do we know whether to add or subtract a symbol's value?

Think about it: when you see IV, you process I and then V. The I isn't added directly because it's followed by a larger value (V). If it was III, each I would be added because it's followed by a smaller or equal value (I).

This gives us a huge hint: we need to look at the next character!

• If the current symbol's value is less than the next symbol's value, it's a subtraction case. We should subtract the current symbol's value.
• Otherwise (if the current symbol's value is greater than or equal to the next symbol's value), it's a standard addition case. We should add the current symbol's value.

This "look ahead" strategy is the key to solving this problem efficiently!

Your Step-by-Step Guide (Approach)

Let's break down how we can implement this "look ahead" strategy:

1. Create a Lookup Table: First things first, we need an easy way to get the integer value for each Roman symbol. A dictionary (or hash map) is perfect for this! It maps each Roman character to its integer value ('I': 1, 'V': 5, etc.).

2. Initialize Result: We'll need a variable, let's call it result, to keep a running total of our integer conversion. Start it at 0.

3. Iterate with a "Look Ahead": We'll loop through the Roman numeral string. However, since we need to compare the current character with the next one, we should stop our loop one character before the end of the string.

   • For each pair of (current_char, next_char):
     • Look up current_char's value (val_current) in our dictionary.
     • Look up next_char's value (val_next) in our dictionary.
     • Condition Check:
       • If val_current < val_next (e.g., 'I' is 1, 'V' is 5, so 1 < 5): This is a subtraction case! Add -val_current to our result.
       • Else (val_current >= val_next): This is an addition case! Add val_current to our result.

4. Handle the Last Character: Our loop stops one character before the end. This means the very last character in the string was never compared as a current_char to a next_char. Since a last character can never be part of a subtraction pair (it has no character after it), its value is always added. So, after the loop, we simply add the value of the last_char to our result.

5. Return: Finally, result holds the complete integer conversion. Return it!

The Code (Python)

Here's the Python solution based on our approach:

class Solution:
    def romanToInt(self, s: str) -> int:
        res = 0  # Initialize our result accumulator

        # Our handy lookup table for Roman symbols to integer values
        roman_map = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }

        # Iterate through the string, comparing current character (a) with the next (b)
        # The zip(s, s[1:]) trick cleverly creates pairs:
        # (s[0], s[1]), (s[1], s[2]), ..., (s[N-2], s[N-1])
        # This processes all pairs *except* for the very last character s[N-1]
        for current_char, next_char in zip(s, s[1:]):
            current_value = roman_map[current_char]
            next_value = roman_map[next_char]

            if current_value < next_value:
                # If current value is smaller than next, it's a subtraction case (e.g., IV, IX)
                res -= current_value
            else:
                # Otherwise, it's a standard addition case (e.g., III, L)
                res += current_value

        # After the loop, the value of the *last* character in the string
        # has not yet been added to `res`. It will always be an addition.
        res += roman_map[s[-1]] 

        return res

Performance Check (Time & Space Complexity)

• Time Complexity: O(N)

  • We iterate through the input string s once using the zip function, which effectively processes each character pair. The length of the string is N.
  • Looking up values in our roman_map (a dictionary) takes O(1) (constant time) on average.
  • Therefore, the total time complexity is directly proportional to the length of the input string.

• Space Complexity: O(1)

  • We use a dictionary (roman_map) to store the symbol-to-value mappings. This dictionary has a fixed size (7 entries), regardless of how long the input Roman numeral string s is.
  • No other data structures are used that grow with the input size.
  • Thus, the auxiliary space used is constant.

Key Takeaways

• Lookahead Pattern: This problem is a classic example of when to use a "lookahead" pattern in string processing. By considering the next element, you can make informed decisions about the current element.
• Hash Maps/Dictionaries are Your Friends: For quick lookups of values associated with specific keys (like Roman symbols to their integers), dictionaries are incredibly efficient and make your code clean.
• Edge Cases Matter: Always consider the beginning, middle, and end of your input. Here, the very last character needed special handling because our zip iteration didn't include a "next" for it.

That's it! You've successfully converted Roman numerals to integers using a clever approach. Keep practicing, and you'll be tackling even more complex problems in no time!