Roman to Integer
Problem
Given a string s representing a Roman numeral, return its integer equivalent.
- 1 ≤ s.length ≤ 15
- s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M')
- It is guaranteed that s is a valid Roman numeral in the range [1, 3999]
Example
s = "MCMXCIV"1994The algorithm processes the string from right to left. Starting with 'V' (5), it adds 5 to total. Next, 'I' (1) is less than previous 'V' (5), so it subtracts 1, resulting in total 4. Then 'C' (100) is greater than previous 'I' (1), so it adds 100, total 104. Next 'X' (10) is less than 'C' (100), so subtract 10, total 94. Then 'M' (1000) is greater than 'X' (10), add 1000, total 1094. Next 'C' (100) is less than 'M' (1000), subtract 100, total 994. Finally 'M' (1000) is greater than 'C' (100), add 1000, total 1994. This stepwise addition and subtraction based on relative values correctly converts the Roman numeral.
Approach
Straightforward Solution
A naive approach would scan left to right, checking pairs of characters to decide whether to add or subtract. This requires careful lookahead and can be error-prone.
Core Observation
Roman numerals are generally additive, but when a smaller numeral precedes a larger one, it indicates subtraction. This means the value of each symbol depends on its relative position to the next symbol.
Path to Optimal
Reversing the string and scanning from right to left simplifies the logic: if the current numeral is less than the previous one seen, subtract it; otherwise, add it. This eliminates the need for lookahead and naturally encodes the subtraction rule.
Optimal Approach
PreviewUse a hash map to map Roman symbols to their integer values. Iterate over the reversed string, maintaining the previous numeral's value…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm iterates through the input string once, performing constant-time operations per character.
Space
O(1)
The hash map has a fixed size of 7 entries, and only a few integer variables are used, resulting in constant auxiliary space.
Pattern Spotlight
Simulation (Stateful Iteration with Relative Comparison)
When a problem involves interpreting a sequence with context-dependent values, simulate the process by iterating with a state variable that tracks the previous element, enabling local decisions that collectively produce the global result.
Solution
| 1 | class Solution: |
| 2 | def romanToInt(self, s: str) -> int: |
| 3 | roman_value = { |
| 4 | "I": 1, |
| 5 | "V": 5, |
| 6 | "X": 10, |
| 7 | "L": 50, |
| 8 | "C": 100, |
| 9 | "D": 500, |
| 10 | "M": 1000, |
| 11 | } |
| 12 | |
| 13 | total = 0 |
| 14 | previous_value = 0 |
| 15 | |
| 16 | for char in reversed(s): |
| 17 | current_value = roman_value[char] |
| 18 | |
| 19 | if current_value < previous_value: |
| 20 | total -= current_value |
| 21 | else: |
| 22 | total += current_value |
| 23 | |
| 24 | previous_value = current_value |
| 25 | |
| 26 | return total |
Step-by-Step Solution
Map Roman Symbols to Integer Values
| 3 | roman_value = { |
| 4 | "I": 1, |
| 5 | "V": 5, |
| 6 | "X": 10, |
| 7 | "L": 50, |
| 8 | "C": 100, |
| 9 | "D": 500, |
| 10 | "M": 1000, |
| 11 | } |
Objective
To create a constant-time lookup for the integer value of each Roman numeral character.
Key Insight
A fixed hash map from Roman symbols to integers enables O(1) access to each symbol's value, which is essential for efficient iteration and comparison. This mapping encodes the fundamental Roman numeral values and is the foundation for the conversion logic.
Interview Quick-Check
Core Logic
The hash map provides direct access to symbol values, enabling the algorithm to quickly determine whether to add or subtract.
Common Pitfalls & Bugs
Forgetting to include all Roman symbols or mistyping values leads to incorrect conversions.
Iterate Over the Roman Numeral in Reverse to Accumulate Total
To traverse the string from right to left, deciding whether to add or subtract each numeral's value based on its relation to the previous numeral.
Return the Computed Integer Total
To output the final integer value after processing all Roman numerals.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 1 Critical line interviewers watch for.
if current_value < previous_value:Check if current value is less than previous value to decide subtraction.
This conditional is the core of the Roman numeral conversion logic, correctly identifying when to subtract a numeral based on its relative value to the previous numeral, enabling accurate interpretation of subtractive notation.
Full line-by-line criticality + rationale for all 19 lines available on Pro.
Test Your Understanding
Why does iterating from right to left and comparing the current numeral to the previous one simplify the conversion logic?
See the answer with Pro.
Related Problems
Simulation pattern
Don't just read it. Drill it.
Reconstruct Roman to Integer from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Roman to Integer drill