Roman to Integer | Leetcode 13 | Mapping and Subtraction Rule Solution

The Roman to Integer problem asks us to convert a given Roman numeral string into its corresponding integer value.

• Roman numerals are represented using seven symbols:
  • I = 1
  • V = 5
  • X = 10
  • L = 50
  • C = 100
  • D = 500
  • M = 1000
• Numbers are formed by combining these symbols and adding their values.
• However, when a smaller value comes before a larger value, it is subtracted instead of added.

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input: s = "III"
Output: 3
Explanation: 1 + 1 + 1 = 3

Example 2

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V = 5, III = 3 → 50 + 5 + 3 = 58

Example 3

Input: s = "MCMXCIV"
Output: 1994
Explanation: 
M = 1000, CM = 900, XC = 90, IV = 4 → 1000 + 900 + 90 + 4 = 1994

Intuition and Approach

To solve the Roman to Integer problem, we need to carefully apply Roman numeral rules:

1. Mapping values:
   • Create a dictionary that maps Roman numerals to their integer values.
2. Traverse the string:
   • For each character, check if its value is less than the next character’s value.
   • If yes → subtract the value (subtractive case, e.g., IV = 4).
   • If no → add the value to the total.
3. Return total:
   • After processing all characters, the accumulated total is the integer equivalent.

This approach works because Roman numerals follow a consistent additive and subtractive rule.

Code Implementation

class Solution:
    def romanToInt(self, s: str) -> int:
        # Mapping Roman numerals to their values
        roman_map = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000
        }
        
        total = 0
        n = len(s)
        
        for i in range(n):
            # If current value is less than the next one, subtract it
            if i + 1 < n and roman_map[s[i]] < roman_map[s[i + 1]]:
                total -= roman_map[s[i]]
            else:
                total += roman_map[s[i]]
        
        return total

Code Explanation

• Mapping: roman_map assigns values to Roman symbols.
• Loop through string:
  • If the current numeral is smaller than the next, subtract it (IV → -1 + 5 = 4).
  • Otherwise, add it normally (VI → 5 + 1 = 6).
• Result: The accumulated total gives the integer equivalent.

Dry Run

Input: s = "MCMXCIV"

• M = 1000 → total = 1000
• C < M → subtract 100 → total = 900
• M = 1000 → total = 1900
• X < C → subtract 10 → total = 1890
• C = 100 → total = 1990
• I < V → subtract 1 → total = 1989
• V = 5 → total = 1994

Output: 1994

Time and Space Complexity

• Time Complexity:
  • Traverse string once → O(N), where N is length of s.
• Space Complexity:
  • Dictionary of fixed size (7 elements) → O(1).

Conclusion

The Roman to Integer problem is solved using a mapping dictionary and the subtraction rule.

• Add values normally unless a smaller numeral precedes a larger one, in which case subtract.
• Runs in O(N) time with O(1) space.
• Efficient and widely used approach for converting Roman numerals to integers.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.