13 - Roman to Integer

Difficulty: Easy | Pattern: Hash Map / String Parsing | Company tags: Amazon, Apple, Facebook, Microsoft

Problem Statement

Roman numerals are represented by seven different symbols: I(1), V(5), X(10), L(50), C(100), D(500), M(1000).

Roman numerals are usually written largest to smallest from left to right. However, when a smaller value precedes a larger value, it means subtraction (e.g., IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900).

Given a roman numeral string s, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3

Example 2:

Input: s = "LVIII"
Output: 58  (L=50, V=5, III=3)

Example 3:

Input: s = "MCMXCIV"
Output: 1994  (M=1000, CM=900, XC=90, IV=4)

Algorithm Flow

Approach: Left-to-Right Scan — O(n)

Key insight: If the current symbol's value is less than the next symbol's value, subtract it. Otherwise, add it.

def romanToInt(s: str) -> int:
    values = {'I': 1, 'V': 5, 'X': 10, 'L': 50,
              'C': 100, 'D': 500, 'M': 1000}
    
    result = 0
    for i in range(len(s)):
        curr = values[s[i]]
        # If not last char and current < next, subtract
        if i + 1 < len(s) and curr < values[s[i+1]]:
            result -= curr
        else:
            result += curr
    
    return result

Dry Run

s = "MCMXCIV" → expected 1994

i	char	curr	next	action	total
0	M	1000	C(100)	1000 gt 100, add	1000
1	C	100	M(1000)	100 lt 1000, subtract	900
2	M	1000	X(10)	1000 gt 10, add	1900
3	X	10	C(100)	10 lt 100, subtract	1890
4	C	100	I(1)	100 gt 1, add	1990
5	I	1	V(5)	1 lt 5, subtract	1989
6	V	5	(none)	add	1994

1994 ✓

Six Subtraction Cases

Notation	Value
IV	4
IX	9
XL	40
XC	90
CD	400
CM	900

Edge Cases

• Single character → its value directly
• All same symbols → sum all
• Input always valid per problem constraints

Complexity

• Time: O(n) — single pass
• Space: O(1) — fixed-size hash map (7 entries)

Key Terms

Term	Definition
Hash map lookup	Constant-time mapping from a roman symbol (I, V, X, ...) to its integer value.
Subtractive notation	A smaller-value symbol placed before a larger one signals subtraction (e.g., IV = 4).
Left-to-right scan	Single pass over the string, deciding add/subtract by comparing each symbol to its successor.
Lookahead comparison	Checking s[i+1] before committing to add or subtract for s[i].

FAQ

Q: Can this be solved without extra space for the hash map? A: You could use if/elif chains or a switch on characters, but that trades readability for a marginal constant-space "win" — the hash map is already O(1) space (max 7 entries), so there's no real gain.

Q: What if the input is empty? A: The loop never executes and result stays 0, which is a reasonable default. The problem constraints guarantee 1 <= s.length, so this is not tested in practice.

Q: How would this change if the input could be invalid roman numerals (e.g., "IIII" or "VV")? A: You'd need an explicit validation pass — checking symbol repetition limits and legal subtractive pairs — since the current approach assumes well-formed input and would silently produce a wrong-but-plausible number.

Q: Why compare s[i] to s[i+1] instead of the previous approach of comparing s[i] to s[i-1]? A: Both directions work, but comparing forward lets you decide immediately whether to add or subtract as you visit each character, avoiding a correction step after the fact.

Q: Is there a way to solve this using string replacement instead of a loop? A: Yes — replace all six subtractive pairs ("IV", "IX", "XL", "XC", "CD", "CM") with placeholder values or spaced-out equivalents, then sum the individual symbol values. It works but is less efficient and less idiomatic than the single-pass scan.

Quick Revision

• Map each of the 7 roman symbols to its integer value with a hash map.
• Scan the string once, left to right.
• If current symbol's value < next symbol's value, subtract current; otherwise add it.
• The last character always gets added (no symbol follows it to compare against).
• Six subtractive pairs exist: IV, IX, XL, XC, CD, CM.
• Time complexity is O(n); space is O(1) (fixed 7-entry map).
• No extra data structures needed beyond the lookup table.
• Input is guaranteed valid per constraints — no need to validate malformed roman numerals.
• This is the mirror problem of Integer to Roman (encoding vs. decoding the same symbol system).

Related Problems

• Integer to Roman — the inverse encoding problem (greedy symbol selection from largest to smallest value). Not yet present in this directory as a separate file.
• 387-FirstUniqueCharacterInAString.md — shares the hash-map-driven single-pass string scan pattern.
• 205-IsomorphicStrings.md — another string problem solved with hash map lookups during a linear scan.