Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
A complete visual walkthrough of converting Roman numerals to integers — from brute force to the elegant one-pass solution.
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900.Given a roman numeral, convert it to an integer.
Example 1:
Input: s = "III" Output: 3 Explanation: III = 3.
Example 2:
Input: s = "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.
Example 3:
Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
1 <= s.length <= 15s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').s is a valid roman numeral in the range [1, 3999].Roman numerals have seven symbols. Most of the time you just add them up. The tricky part is the six subtractive combinations like IV (4), IX (9), XL (40), XC (90), CD (400), and CM (900).
A brute force approach would explicitly check for every two-character subtractive pair before handling single characters:
// Brute force: check every pair manually if (s.startsWith("CM", i)) { result += 900; i += 2; } else if (s.startsWith("CD", i)) { result += 400; i += 2; } else if (s.startsWith("XC", i)) { result += 90; i += 2; } else if (s.startsWith("XL", i)) { result += 40; i += 2; } else if (s.startsWith("IX", i)) { result += 9; i += 2; } else if (s.startsWith("IV", i)) { result += 4; i += 2; } else { result += map(s.charAt(i)); i += 1; }
// Brute force: check every pair manually if strings.HasPrefix(s[i:], "CM") { result += 900; i += 2 } else if strings.HasPrefix(s[i:], "CD") { result += 400; i += 2 } else if strings.HasPrefix(s[i:], "XC") { result += 90; i += 2 } else if strings.HasPrefix(s[i:], "XL") { result += 40; i += 2 } else if strings.HasPrefix(s[i:], "IX") { result += 9; i += 2 } else if strings.HasPrefix(s[i:], "IV") { result += 4; i += 2 } else { result += romanVal(s[i]); i += 1 }
# Brute force: check every pair manually if s[i:i+2] == "CM": result += 900; i += 2 elif s[i:i+2] == "CD": result += 400; i += 2 elif s[i:i+2] == "XC": result += 90; i += 2 elif s[i:i+2] == "XL": result += 40; i += 2 elif s[i:i+2] == "IX": result += 9; i += 2 elif s[i:i+2] == "IV": result += 4; i += 2 else: result += roman_map(s[i]); i += 1
// Brute force: check every pair manually if s[i..].starts_with("CM") { result += 900; i += 2; } else if s[i..].starts_with("CD") { result += 400; i += 2; } else if s[i..].starts_with("XC") { result += 90; i += 2; } else if s[i..].starts_with("XL") { result += 40; i += 2; } else if s[i..].starts_with("IX") { result += 9; i += 2; } else if s[i..].starts_with("IV") { result += 4; i += 2; } else { result += roman_val(bytes[i]); i += 1; }
// Brute force: check every pair manually if (s.startsWith("CM", i)) { result += 900; i += 2; } else if (s.startsWith("CD", i)) { result += 400; i += 2; } else if (s.startsWith("XC", i)) { result += 90; i += 2; } else if (s.startsWith("XL", i)) { result += 40; i += 2; } else if (s.startsWith("IX", i)) { result += 9; i += 2; } else if (s.startsWith("IV", i)) { result += 4; i += 2; } else { result += map(s[i]); i += 1; }
This works, but it is verbose, error-prone, and hard to extend. Six special cases, each handled explicitly. There is a much more elegant pattern hiding in plain sight.
Notice the pattern: In every subtractive case (IV, IX, XL, XC, CD, CM), a smaller value appears immediately before a larger value. That observation is the key to everything.
Instead of checking for specific pairs, we can use a single universal rule that handles all cases automatically:
Scan left to right. If the current value is less than the next value,
subtract it. Otherwise, add it.
Let's see why this works with "MCMXCIV" (1994):
Why does this work? Roman numerals are written largest-to-smallest (left to right). When a smaller value precedes a larger one, it always means subtraction (like IV = 4, not 1+5). The rule exploits this structural property to eliminate all special-case logic.
Let's trace through "MCMXCIV" step by step, watching the running total build up to 1994:
| i | Char | Value | Next | curr < next? | Action | Running Total |
|---|---|---|---|---|---|---|
| 0 | M | 1000 | C (100) | 1000 < 100? No | + 1000 | 1000 |
| 1 | C | 100 | M (1000) | 100 < 1000? Yes | - 100 | 900 |
| 2 | M | 1000 | X (10) | 1000 < 10? No | + 1000 | 1900 |
| 3 | X | 10 | C (100) | 10 < 100? Yes | - 10 | 1890 |
| 4 | C | 100 | I (1) | 100 < 1? No | + 100 | 1990 |
| 5 | I | 1 | V (5) | 1 < 5? Yes | - 1 | 1989 |
| 6 | V | 5 | none (0) | 5 < 0? No | + 5 | 1994 |
Notice the pairs: The subtracted C(-100) and the following M(+1000) together give CM = 900. Likewise, X(-10) + C(+100) = XC = 90, and I(-1) + V(+5) = IV = 4. The rule naturally decomposes 1994 = 1000 + 900 + 90 + 4.
The beauty of the one-rule approach is that it handles every case uniformly. Still, it is worth verifying the boundaries:
Constraint note: The problem guarantees the input is a valid Roman numeral in the range [1, 3999]. No need to validate the input string, but in a production system you would add checks for invalid characters and malformed sequences.
class Solution { public int romanToInt(String s) { // Map each Roman symbol to its integer value Map<Character, Integer> map = Map.of( 'I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000 ); int result = 0; for (int i = 0; i < s.length(); i++) { // Get the value of the current character int curr = map.get(s.charAt(i)); // Peek at the next character (0 if at end) int next = (i + 1 < s.length()) ? map.get(s.charAt(i + 1)) : 0; // THE RULE: smaller before larger → subtract if (curr < next) result -= curr; // subtractive case (IV, IX, XL...) else result += curr; // normal additive case } return result; } }
func romanToInt(s string) int { // Map each Roman symbol to its integer value romanMap := map[byte]int{ 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000, } result := 0 for i := 0; i < len(s); i++ { // Get the value of the current character curr := romanMap[s[i]] // Peek at the next character (0 if at end) next := 0 if i+1 < len(s) { next = romanMap[s[i+1]] } // THE RULE: smaller before larger → subtract if curr < next { result -= curr // subtractive case (IV, IX, XL...) } else { result += curr // normal additive case } } return result }
class Solution: def roman_to_int(self, s: str) -> int: # Map each Roman symbol to its integer value roman_map = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000, } result = 0 for i in range(len(s)): # Get the value of the current character curr = roman_map[s[i]] # Peek at the next character (0 if at end) nxt = roman_map[s[i + 1]] if i + 1 < len(s) else 0 # THE RULE: smaller before larger → subtract if curr < nxt: result -= curr # subtractive case (IV, IX, XL...) else: result += curr # normal additive case return result
impl Solution { pub fn roman_to_int(s: String) -> i32 { let bytes = s.as_bytes(); // Map each Roman symbol to its integer value let roman_val = |b: u8| -> i32 { match b { b'I' => 1, b'V' => 5, b'X' => 10, b'L' => 50, b'C' => 100, b'D' => 500, b'M' => 1000, _ => 0, } }; let mut result = 0; for i in 0..bytes.len() { // Get the value of the current character let curr = roman_val(bytes[i]); // Peek at the next character (0 if at end) let next = if i + 1 < bytes.len() { roman_val(bytes[i + 1]) } else { 0 }; // THE RULE: smaller before larger → subtract if curr < next { result -= curr; // subtractive case (IV, IX, XL...) } else { result += curr; // normal additive case } } result } }
function romanToInt(s: string): number { // Map each Roman symbol to its integer value const map: Record<string, number> = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000, }; let result = 0; for (let i = 0; i < s.length; i++) { // Get the value of the current character const curr = map[s[i]]; // Peek at the next character (0 if at end) const next = (i + 1 < s.length) ? map[s[i + 1]] : 0; // THE RULE: smaller before larger → subtract if (curr < next) result -= curr; // subtractive case (IV, IX, XL...) else result += curr; // normal additive case } return result; }
Why left-to-right? This approach scans forward, comparing each character with the next. Alternatively, you can scan right-to-left and compare with the previous value. Both achieve O(n) with O(1) space. The left-to-right version shown here is arguably the most readable.
Enter any Roman numeral and step through the algorithm character by character. Watch the add/subtract decisions and running total update in real time.
We make a single pass through the string of length n, doing O(1) work per character: one hash map lookup for the current value, one for the next value, and one comparison to decide add or subtract. The hash map itself has exactly 7 entries, so it uses constant space regardless of input size.
A single loop scans left to right with six explicit if/else branches checking for two-character subtractive pairs (CM, CD, XC, XL, IX, IV). Each match consumes two characters, otherwise one. The loop touches each character once for O(n), using only a result integer and index variable.
One pass through the string with a single comparison per character: look up the current and next values in a 7-entry hash map, then add or subtract based on whether current is less than next. Two O(1) map lookups per iteration yield O(n) total, with only the fixed-size map and a result variable in memory.
The subtraction rule (IV, IX, XL, XC, CD, CM) adds exactly one lookahead comparison per character. Instead of six explicit if/else branches for subtractive pairs, the simple rule "if current < next, subtract" handles all cases with zero special-case code. Both approaches are O(n), but the lookahead version is cleaner and impossible to get wrong.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.