Problem Description

This problem asks you to convert a Roman numeral string into its corresponding integer value.

Roman numerals use seven symbols with specific values:

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

Normally, Roman numerals are written from largest to smallest, left to right, and you simply add up all the values. For example:

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

However, there's a special subtraction rule for certain combinations. When a smaller value appears before a larger value, you subtract the smaller from the larger:

• IV = 5 - 1 = 4 (not IIII)
• IX = 10 - 1 = 9 (not VIIII)

The valid subtraction pairs are:

• I before V or X (making 4 or 9)
• X before L or C (making 40 or 90)
• C before D or M (making 400 or 900)

The solution uses a clever approach: it examines consecutive pairs of characters in the string. If the first character in a pair has a smaller value than the second, it subtracts that value; otherwise, it adds it. The last character is always added since it has no character after it to compare with.

For example, with MCMXCIV (1994):

• M (1000) < C (100)? No, add 1000
• C (100) < M (1000)? Yes, subtract 100
• M (1000) < X (10)? No, add 1000
• X (10) < C (100)? Yes, subtract 10
• C (100) < I (1)? No, add 100
• I (1) < V (5)? Yes, subtract 1
• V (5) is the last character, add 5
• Total: 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994

Intuition

The key insight comes from observing the pattern in Roman numeral subtraction cases. When we see IV (4), we're essentially computing V - I = 5 - 1. This happens whenever a smaller value precedes a larger one.

Let's think about how we'd manually process a Roman numeral like MCMXCIV:

• We read left to right
• Most of the time, we add values together
• But occasionally, we need to subtract when we spot patterns like CM or IV

The clever realization is that we can determine whether to add or subtract by comparing adjacent characters. For any character in the string (except the last one), we can ask: "Is my value less than the character to my right?"

• If yes, subtract my value (because I'm part of a subtraction pair)
• If no, add my value (normal addition case)

For example, in XIV:

• X (10) compared to I (1): 10 > 1, so add 10
• I (1) compared to V (5): 1 < 5, so subtract 1
• V (5) is last, so add 5
• Result: 10 - 1 + 5 = 14

This approach elegantly handles all subtraction cases without explicitly checking for IV, IX, XL, XC, CD, or CM. We don't need to memorize these special pairs - the rule "smaller before larger means subtract" covers them all.

The pairwise function creates overlapping pairs (s[0], s[1]), (s[1], s[2]), etc., allowing us to examine each character with its neighbor. The final character is handled separately since it has no right neighbor and is always added.

Learn more about Math patterns.

Solution Approach

The implementation uses a hash table combined with a clever traversal pattern to convert Roman numerals to integers.

Step 1: Create a Hash Table

First, we build a dictionary d that maps each Roman numeral character to its integer value:

d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}

This allows us to quickly look up the value of any character in O(1) time.

Step 2: Process Adjacent Pairs

The core logic uses Python's pairwise function to create overlapping pairs from the string. For a string like "XIV", pairwise(s) generates:

• ('X', 'I')
• ('I', 'V')

For each pair (a, b), we determine whether to add or subtract the value of a:

(-1 if d[a] < d[b] else 1) * d[a]

This expression works as follows:

• If d[a] < d[b] (smaller value before larger), multiply d[a] by -1 (subtract)
• Otherwise, multiply d[a] by 1 (add)

Step 3: Handle the Last Character

Since pairwise only processes characters that have a neighbor to the right, the last character isn't included in any pair. We always add it to our sum:

+ d[s[-1]]

Complete Process Example

For s = "MCMXCIV" (1994):

1. Pairs generated: ('M','C'), ('C','M'), ('M','X'), ('X','C'), ('C','I'), ('I','V')
2. Processing each pair:
   • M,C: 1000 > 100, add 1000
   • C,M: 100 < 1000, subtract 100
   • M,X: 1000 > 10, add 1000
   • X,C: 10 < 100, subtract 10
   • C,I: 100 > 1, add 100
   • I,V: 1 < 5, subtract 1
3. Add last character V: 5
4. Sum: 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994

The entire computation is done in a single line using sum() with a generator expression, making it both concise and efficient with O(n) time complexity where n is the length of the string.

Example Walkthrough

Let's walk through converting the Roman numeral "XLIV" (which equals 44) using our solution approach.

Step 1: Set up our value mapping

d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}

Step 2: Generate pairs from the string "XLIV"

Using pairwise("XLIV"), we get three pairs:

• Pair 1: ('X', 'L')
• Pair 2: ('L', 'I')
• Pair 3: ('I', 'V')

Step 3: Process each pair

For each pair (a, b), we check if d[a] < d[b]:

• Pair 1: ('X', 'L')

  • d['X'] = 10, d['L'] = 50
  • Is 10 < 50? Yes → Subtract 10
  • Contribution: -10

• Pair 2: ('L', 'I')

  • d['L'] = 50, d['I'] = 1
  • Is 50 < 1? No → Add 50
  • Contribution: +50

• Pair 3: ('I', 'V')

  • d['I'] = 1, d['V'] = 5
  • Is 1 < 5? Yes → Subtract 1
  • Contribution: -1

Step 4: Add the last character

The last character 'V' has no pair partner, so we always add it:

• d['V'] = 5
• Contribution: +5

Step 5: Calculate the total

Sum all contributions:

-10 + 50 - 1 + 5 = 44

The algorithm correctly identifies that:

• XL represents 40 (50 - 10)
• IV represents 4 (5 - 1)
• Together they form 44

This demonstrates how comparing adjacent characters automatically handles the subtraction cases without explicitly checking for specific patterns like XL or IV.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the string using pairwise(s), which generates pairs of consecutive characters. This creates n-1 pairs for a string of length n. Each pair operation involves:

• Two dictionary lookups: d[a] and d[b] - both O(1) operations
• One comparison: d[a] < d[b] - O(1) operation
• One multiplication: (-1 if ... else 1) * d[a] - O(1) operation

After processing all pairs, there's one additional dictionary lookup for the last character: d[s[-1]] - O(1) operation.

The sum() function iterates through all n-1 pair results plus the final character value, performing n additions in total.

Since we perform a constant amount of work for each character in the string, the overall time complexity is O(n), where n is the length of the input string s.

Space Complexity: O(m)

The space usage consists of:

• The dictionary d containing 7 key-value pairs representing Roman numerals - O(7) = O(m) where m is the size of the character set (7 in this case)
• The pairwise() iterator generates pairs on-the-fly without storing all pairs in memory - O(1) additional space
• The generator expression inside sum() produces values one at a time - O(1) additional space

Therefore, the overall space complexity is O(m), where m represents the size of the character set used in the Roman numeral system.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Python Version Compatibility Issue

The pairwise function is only available in Python 3.10+. If you're using an earlier version or submitting to a platform that doesn't support Python 3.10, the code will fail with an ImportError.

Solution: Implement your own pairwise logic using zip:

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_to_value = {
            'I': 1, 'V': 5, 'X': 10, 'L': 50, 
            'C': 100, 'D': 500, 'M': 1000
        }
      
        result = 0
        # Use zip to create pairs manually
        for i in range(len(s) - 1):
            if roman_to_value[s[i]] < roman_to_value[s[i + 1]]:
                result -= roman_to_value[s[i]]
            else:
                result += roman_to_value[s[i]]
      
        # Add the last character
        result += roman_to_value[s[-1]]
        return result

2. Forgetting to Handle the Last Character

A common mistake is only processing the pairs and forgetting that the last character isn't part of any pair. Since pairwise creates overlapping pairs, the last character never appears as the first element of a pair.

What happens if you forget: For "XIV" (14), without adding the last character 'V', you'd get 10 - 1 = 9 instead of 14.

Solution: Always remember to add roman_to_value[s[-1]] after processing all pairs.

3. Incorrect Subtraction Logic

Mixing up when to subtract vs. add. The rule is: subtract when a smaller value appears BEFORE a larger value, not after.

Wrong approach:

# Incorrect: checking if current is greater than next
if roman_to_value[current] > roman_to_value[next_char]:
    result -= roman_to_value[current]  # Wrong!

Correct approach:

# Correct: subtract when current is less than next
if roman_to_value[current] < roman_to_value[next_char]:
    result -= roman_to_value[current]

4. Edge Case: Single Character Input

If the input is a single character like "V", using s[-1] works fine, but iterating through pairs might cause issues if not handled properly.

Solution: The current implementation handles this correctly since pairwise of a single character returns an empty iterator, and the sum would be 0, then we add s[-1] which gives the correct result. However, if implementing manually, consider adding a check:

if len(s) == 1:
    return roman_to_value[s[0]]

5. Using Dictionary Name 'd' Instead of Descriptive Name

While the original solution uses d as the dictionary name, this can lead to confusion when debugging or maintaining code.

Solution: Use a descriptive name like roman_to_value or roman_map to make the code more readable and self-documenting.