Roman to Integer
Convert a Roman numeral to an integer in one pass with a symbol-value map: subtract a symbol that is smaller than the next one, otherwise add it.
Problem Understanding
Roman to Integer: convert a valid Roman numeral (1 to 3999) to an integer. Symbols are I 1, V 5, X 10, L 50, C 100, D 500, M 1000. They are written largest to smallest, except in six subtraction pairs: IV 4, IX 9, XL 40, XC 90, CD 400, CM 900.
Example: "MCMXCIV" returns 1994 (M = 1000, CM = 900, XC = 90, IV = 4).
The Intuition: Look One Symbol Ahead
Store the seven symbol values in a hash map (or a switch) for O(1) lookups. Then one rule handles every case:
- If the current symbol is smaller than the next one, it is the first half of a subtraction pair: subtract it.
- Otherwise add it.
IV is -1 + 5 = 4; VI is 5 + 1 = 6. There is no need to list the six pairs. Like Two Sum, the map turns each step into a constant-time lookup.
Interactive Walkthrough
Each symbol shows its value underneath. The current symbol is filled and the next one is marked, since that comparison decides the step. Subtracted symbols turn orange and added ones green. Try Every pair for a numeral built entirely from subtraction pairs.
Dry Run Table
Input: s = "MCMXCIV"
| Symbol | Value | Next | Action | Total |
|---|---|---|---|---|
| M | 1000 | C (100) | add | 1000 |
| C | 100 | M (1000) | subtract | 900 |
| M | 1000 | X (10) | add | 1900 |
| X | 10 | C (100) | subtract | 1890 |
| C | 100 | I (1) | add | 1990 |
| I | 1 | V (5) | subtract | 1989 |
| V | 5 | — | add | 1994 |
Answer: 1994.
The Solution Template
A value map and a one-symbol look-ahead. C uses a switch instead of a map.
Roman to Integer Code
1var romanToInt = function(s) {2 const value = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };3 let total = 0;4 for (let i = 0; i < s.length; i++) {5 const v = value[s[i]];6 if (i + 1 < s.length && v < value[s[i + 1]]) total -= v;7 else total += v;8 }9 return total;10};
Edge Cases & Common Mistakes
- Last symbol: it has no next symbol, so it is always added; guard the look-ahead with
i + 1 < n. - Equal neighbours (
II,XX): equal is not smaller, so both are added. - Subtracting the pair twice: handle only the smaller symbol with the look-ahead; the larger one is then added normally.
- Single symbol:
"M"is 1000; the loop adds it. - Integer to Roman: the reverse problem, Integer to Roman (LeetCode 12), walks the same value table greedily from 1000 down to 1.
Summary
Map each symbol to its value. Walk the string once: subtract a symbol that is smaller than the one after it, add every other symbol. O(n) time and O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet