Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Map each Roman symbol to its value, then scan the string once. The whole problem is the subtractive rule: a symbol is subtracted instead of added exactly when its value is smaller than the symbol to its right (IV = 5 − 1). Add otherwise. O(n) time, O(1) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you discover the subtractive rule yourself from examples instead of hard-coding the six special pairs, and whether you write a clean single pass with a correct lookahead bound.
Where candidates slip
Hard-coding the six two-letter combinations with string replacement, or comparing in the wrong direction and subtracting when you should add.
How to stand out
Derive 'subtract when a larger symbol follows' from IV and IX, mention the equivalent right-to-left scan that drops the bounds check, and note there are exactly six subtractive pairs so the rule is complete.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewAt symbol s[i]Is there a next symbol s[i+1]?No (last)YesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Single Pass with Lookahead (Optimal)
1Hint 1Explore hintHide hint
Compare IV (4) with VI (6). Same two symbols, different order. What does the *position* of the smaller symbol tell you about whether to add or subtract it?
2Hint 2Explore hintHide hint
Map each symbol to its value. Scan left to right. For symbol i, peek at symbol i+1: if i's value is smaller, this is a subtractive pair, so subtract; otherwise add.
3Hint 3Explore hintHide hint
Guard the peek at the last index (no i+1 there — always add it). The map is fixed size, so space is O(1).
A · Core idea
Roman numerals are almost a plain sum of symbol values — LVIII is just 50 + 5 + 1 + 1 + 1. The only wrinkle is the subtractive notation, and the elegant realization is that you never have to recognize the six special two-letter tokens by name. You only have to notice a local ordering inversion.
The rule, derived from two examples. Look at IV = 4 and VI = 6. In both, I is worth 1 and V is worth 5; the only difference is order. When the smaller symbol (I) comes before the larger (V), it's subtracted; when it comes after, it's added. Generalize: a symbol at position i is subtracted exactly when value[s[i]] < value[s[i+1]]. That single comparison subsumes all six subtractive pairs — IV, IX, XL, XC, CD, CM — without ever spelling them out.
Why lookahead and not pattern matching. A tempting but clumsy approach is to string-replace "IV" → "IIII" and friends, or to scan two characters at a time and branch on which compound token you see. Both work but are noisy and error-prone. The lookahead version treats every symbol uniformly: add its value, unless the next symbol is larger, in which case subtract. The hash map's only job is turning a character into its integer weight; all the intelligence lives in the comparison value[s[i]] < value[s[i+1]].
Why the bounds guard matters. At the final index there is no s[i+1] to peek at. The last symbol of a valid numeral is always the smallest-or-equal trailing symbol, so it is always added — and the guard i + 1 < n makes that fall through to the add branch naturally. Forget the guard and you index out of bounds; that's the one boundary bug in an otherwise trivial loop.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "MCMXCIV"Interactive diagram
MCMXCIV broken into pairs
i=0 'M'(1000)Three subtractive pairs (CM, XC, IV) plus a leading M. The local rule handles all of them uniformly.
1994C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The problem looks like it needs you to memorize six special cases, but they all collapse into one local rule: 'subtract a symbol when a larger one is immediately to its right.' Recognizing that a set of special cases is really one underlying rule is the meta-skill — it turns a lookup table into a single comparison.
ComplexityO(n) time, O(1) space — One pass over n ≤ 15 characters, each doing O(1) map lookups and a comparison. The map has 7 fixed entries, so space is constant.
E · Edge cases and pitfalls6s = "I" — Single symbol, no lookahead → add 1 → returns 1.Explore edge casesHide edge cases
Edge cases handled
s = "I"Single symbol, no lookahead → add 1 → returns 1.s = "MMMCMXCIX"3999, the max. CM(900)+XC(90)+IX(9) handled as three subtractive pairs → 3999.s = "IV"i=0 'I'(1) < 'V'(5) → subtract 1; i=1 'V'(5) last → add 5 → 4.
Pitfalls
- Omitting the i + 1 < length guard — out-of-bounds read on the last symbol.
- Comparing in the wrong direction (next < cur) — subtracts the larger symbol and corrupts the total.
- Hard-coding the six pairs with string replacement — works but is brittle and misses the underlying rule.
Approach 2 of 2
Right-to-Left Scan (No Bounds Check)
1Hint 1Explore hintHide hint
If you scan from the RIGHT, the 'next bigger symbol' you'd peek at is the one you just processed. Can you track it in a single variable instead of indexing ahead?
2Hint 2Explore hintHide hint
Keep `prev` = the value of the symbol immediately to the right. If the current value is smaller than prev, subtract it; otherwise add. Then set prev = current.
3Hint 3Explore hintHide hint
Starting prev at 0 means the rightmost symbol is always added (nothing smaller than 0 from the right). No i+1 bounds check needed.
A · Core idea
This is the same subtractive rule viewed from the other end. Instead of peeking forward at s[i+1], we walk right to left and remember the value of the symbol we just saw (which sits to the current symbol's right). The decision becomes: if the current value is smaller than that neighbor, subtract; otherwise add.
Why it's marginally cleaner. The left-to-right version needs an i + 1 < n guard so the lookahead doesn't fall off the end. Scanning right to left, the 'neighbor to the right' is simply the previous iteration's value, stored in a variable prev. Initializing prev = 0 makes the rightmost symbol add unconditionally (no Roman value is below 0), so there is no boundary case to special-case at all.
Same rule, mirrored. It's worth saying out loud that this isn't a different algorithm — it's the identical 'subtract when a larger symbol is adjacent on the right' rule, just evaluated in reverse order so the comparison target is already in hand. Either direction is O(n) time and O(1) space; pick whichever reads more clearly to you. Many people find the prev-variable version less error-prone precisely because it eliminates index arithmetic.
When this framing pays off. Tracking 'the relevant neighbor' in a rolling variable instead of indexing into the array is a broadly useful trick — it shows up in array problems where each element's contribution depends on an adjacent one. Recognizing that a lookahead can become a lookbehind with a saved variable is a small but transferable insight.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "MCMXCIV"'V'(5)
prev=0, 5<0? no → add
total = 5, prev = 51994C · Code with teaching comments
Reference implementation previewpublic int romanToInt(String s) { Map<Character, Integer> value = Map.of( 'I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000); int total = 0, prev = 0;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
A forward lookahead and a backward 'remember the previous value' are interchangeable. When a bounds guard is annoying you, flipping the scan direction often makes it disappear because the neighbor you need is already computed.
ComplexityO(n) time, O(1) space — Still one pass over n characters with O(1) work each. A single int `prev` replaces the lookahead, so space stays O(1).
E · Edge cases and pitfalls5s = "IX" — From right: X(10) added (prev 0); I(1)<10 → subtract → 9.Explore edge casesHide edge cases
Edge cases handled
s = "IX"From right: X(10) added (prev 0); I(1)<10 → subtract → 9.s = "MMM"Each 1000 ≥ prev → all added → 3000.
Pitfalls
- Forgetting to update prev each iteration — every comparison then uses the stale rightmost value.
- Initializing prev to a large number — would wrongly subtract the rightmost symbol.
- Mixing directions: comparing cur < prev while still scanning left to right.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int romanToInt(String s) { Map<Character, Integer> value = new HashMap<>(); value.put('I', 1); value.put('V', 5); value.put('X', 10); value.put('L', 50); value.put('C', 100); value.put('D', 500); value.put('M', 1000);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Summing every symbol (ignoring subtraction)
Treating the numeral as a plain sum gives the right answer for descending strings like 'LVIII' but overcounts subtractive ones: 'IV' becomes 1 + 5 = 6 instead of 4.
Explore the code comparisonHide the code comparison
Summing every symbol (ignoring subtraction)
Treating the numeral as a plain sum gives the right answer for descending strings like 'LVIII' but overcounts subtractive ones: 'IV' becomes 1 + 5 = 6 instead of 4.
Don't write this
total = 0
for c in s:
total += value[c] # 'IV' -> 6, wrong
return totalWrite this instead
for i in range(n):
if i + 1 < n and value[s[i]] < value[s[i + 1]]:
total -= value[s[i]]
else:
total += value[s[i]]2Out-of-bounds lookahead
On the last symbol there is no s[i+1]. Reading it without guarding throws StringIndexOutOfBounds / IndexError.
Explore the code comparisonHide the code comparison
Out-of-bounds lookahead
On the last symbol there is no s[i+1]. Reading it without guarding throws StringIndexOutOfBounds / IndexError.
Don't write this
if (cur < value.get(s.charAt(i + 1))) { // throws when i is the last index
total -= cur;
}Write this instead
if (i + 1 < s.length() && cur < value.get(s.charAt(i + 1))) {
total -= cur;
}3Comparing in the wrong direction
Subtraction applies to the SMALLER symbol that precedes a larger one. Comparing next < cur subtracts the larger symbol and produces garbage.
Explore the code comparisonHide the code comparison
Comparing in the wrong direction
Subtraction applies to the SMALLER symbol that precedes a larger one. Comparing next < cur subtracts the larger symbol and produces garbage.
Don't write this
if i + 1 < n and value[s[i + 1]] < value[s[i]]:
total -= value[s[i]] # subtracts the bigger symbolWrite this instead
if i + 1 < n and value[s[i]] < value[s[i + 1]]:
total -= value[s[i]] # subtracts the smaller leading symbolRevise
Carry the pattern into the interview
Pattern to remember
Single-pass scan with one-symbol lookahead
Code pattern to memorize
value = {I:1, V:5, X:10, L:50, C:100, D:500, M:1000}
total = 0
for i in 0..n:
if i+1 < n and value[s[i]] < value[s[i+1]]:
total -= value[s[i]] # subtractive pair (IV, IX, XL...)
else:
total += value[s[i]]
return totalRules to remember
- 1The only special case is the subtractive pair. A symbol is subtracted iff a larger symbol follows it —
value[s[i]] < value[s[i+1]]. - 2There are exactly six subtractive pairs: IV(4), IX(9), XL(40), XC(90), CD(400), CM(900). Everything else is plain addition.
- 3Lookahead, not lookbehind, keeps the loop simple — but a right-to-left scan comparing to the previous symbol is equally valid and needs no bounds check.
- 4Guard the lookahead. At the last index there is no
s[i+1]; that symbol is always added. - 5No need to detect or validate compound tokens like "IV" explicitly — the value comparison handles them implicitly.
Use this pattern when
- Converting a positional/encoded numeral system to a number
- Each symbol's contribution depends on a neighbor (context-sensitive single pass)
- Fixed, tiny symbol alphabet that maps cleanly to integer weights
- You can decide add-vs-subtract by comparing adjacent elements
Choose another pattern when
- Converting integer → Roman → that's the reverse problem (greedy with a value table)
- Arbitrary-precision or non-fixed symbol sets → parser/grammar, not a lookup
- Validating whether the Roman string is well-formed → a stricter, rule-checking problem
- Symbols whose value depends on more than one neighbor → needs real parsing
Interview takeaway
Roman to Integer is the canonical 'a token's meaning depends on its neighbor' problem. Once you see the subtractive rule as `add unless a bigger symbol is to the right`, the code is six lines. The hash map just turns symbols into weights; the insight is the comparison, not the map.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternContext-sensitive single-pass scan: a token's contribution depends on its neighbor. The subtractive rule is the teaching point — many encoding problems reduce to 'add this unless an adjacent element changes its meaning.' The hash map is incidental; the adjacency comparison is the pattern.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Integer to RomanThe reverse: greedily subtract the largest value (including the six subtractive tokens) from the number, appending symbols.
- Integer to English WordsComing soonAnother encode-a-number-as-symbols problem; group by thousands and map each chunk to words.
- String to Integer (atoi)Parsing characters into a number with positional rules — same 'scan and accumulate' spirit, different rule set.