Roman to Integer Conversion in DSA Python

Mental Model

Roman numerals are letters that represent numbers. We add or subtract values based on their order to get the final number.

Analogy: Think of reading a price tag where some discounts apply if a smaller number comes before a bigger number, so you subtract instead of add.

R O M A N  N U M E R A L S
I  V  X  L  C  D  M
1  5 10 50 100 500 1000

Dry Run Walkthrough

Input: Roman numeral: 'MCMIV'

Goal: Convert 'MCMIV' to its integer value

Step 1: Read 'M' (1000), add 1000 to total

Total = 1000

Why: Start with the first symbol's value

Step 2: Read 'C' (100), next is 'M' (1000), since 100 < 1000, subtract 100

Total = 1000 - 100 = 900

Why: Smaller before bigger means subtract

Step 3: Read 'M' (1000), next is 'I' (1), since 1000 > 1, add 1000

Total = 900 + 1000 = 1900

Why: Bigger or equal means add

Step 4: Read 'I' (1), next is 'V' (5), since 1 < 5, subtract 1

Total = 1900 - 1 = 1899

Why: Smaller before bigger means subtract

Step 5: Read 'V' (5), no next symbol, add 5

Total = 1899 + 5 = 1904

Why: Last symbol always adds

Result:

Total = 1904

Annotated Code

DSA Python

class RomanToInteger:
    def __init__(self):
        self.values = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}

    def roman_to_int(self, s: str) -> int:
        total = 0
        for i in range(len(s)):
            value = self.values[s[i]]
            if i + 1 < len(s) and self.values[s[i]] < self.values[s[i + 1]]:
                total -= value  # subtract if smaller before bigger
            else:
                total += value  # add otherwise
        return total


# Driver code
converter = RomanToInteger()
result = converter.roman_to_int('MCMIV')
print(result)

for i in range(len(s)):

iterate over each Roman numeral character

value = self.values[s[i]]

get integer value of current Roman numeral

if i + 1 < len(s) and self.values[s[i]] < self.values[s[i + 1]]:

check if current value is less than next value to decide subtraction

total -= value # subtract if smaller before bigger

subtract current value from total

else:

otherwise add current value

total += value # add otherwise

add current value to total

Output

1904

Complexity Analysis

Time: O(n) because we scan each character once

Space: O(1) because the map of Roman numerals is fixed size

vs Alternative: This is more efficient than parsing substrings or using recursion which may add overhead

Edge Cases

Empty string

Returns 0 as no numerals to convert

DSA Python

for i in range(len(s)):

Single character like 'V'

Returns the value of that single numeral

DSA Python

if i + 1 < len(s) and self.values[s[i]] < self.values[s[i + 1]]:

All numerals in descending order like 'MDCLXVI'

All values are added correctly

DSA Python

else:

When to Use This Pattern

When you see a problem asking to convert Roman numerals to numbers, use the subtract-if-smaller-before-bigger pattern to handle special cases.

Common Mistakes

Mistake: Always adding values without checking the next numeral causes wrong totals for subtractive cases.
Fix: Add a check to subtract when current numeral is smaller than the next one.

Summary

Converts Roman numeral strings to integer numbers by adding or subtracting values based on order.

Use when you need to interpret Roman numerals as numbers in programs.

Remember to subtract when a smaller numeral comes before a larger one, otherwise add.