A roman numeral is just a sum of symbol values — except for six special pairs. The pattern insight is the subtractive-pair rule: a symbol whose value is strictly smaller than the symbol to its right does not add itself; it subtracts from the running total (it discounts the bigger neighbor that follows it). Everything else just adds its face value. Once you see that, the whole problem collapses into a single left-to-right scan where each symbol only needs to compare itself against the next one — never the rest of the string.
Brute Force
Time O(n²)Space O(1)Take the rule literally: a symbol is subtracted if and only if some larger-valued symbol occurs anywhere to its right. For each symbol (at index i) that means scanning the whole suffix from i + 1 to the end to look for any strictly larger value — a nested loop. It is correct because subtractive pairs always sit so that the small symbol has a bigger value ahead, but it is needlessly expensive: every early symbol re-examines almost the entire remaining string.
class Solution: def romanToInt(self, s: str) -> int: values = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000, } total = 0 n = len(s) for i in range(n): v = values[s[i]] # Subtractive iff a larger value appears to the right. if any(values[s[j]] > v for j in range(i + 1, n)): total -= v else: total += v return totalWhy it is quadratic: the any(...) check walks the entire suffix for each of the n positions, so this is n + (n-1) + ... + 1 ≈ n²/2 comparisons — O(n²) time. It gets every answer right (e.g. for IV, the I finds a 5 ahead and subtracts), but it re-reads the tail of the string for every symbol even though only the immediate neighbor can ever matter. Space is O(1) aside from the fixed lookup table.
Single Pass Comparing Next
OptimalTime O(n)Space O(1)A valid roman numeral only ever subtracts when the symbol immediately to its left is smaller than the one immediately after — a contiguous (small, big) pair. So you never need to look further than one symbol ahead. Scan left to right; at each symbol, compare its value with the next symbol’s value. If current is strictly smaller, subtract it (it is the small half of a subtractive pair); otherwise add it. The last symbol has no next, so it always adds.
class Solution: def romanToInt(self, s: str) -> int: values = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000, } total = 0 n = len(s) for i in range(n): v = values[s[i]] if i + 1 < n and v < values[s[i + 1]]: total -= v # small half of a subtractive pair else: total += v return totalWatch the one-glance-past pointer + per-symbol decision on the file example, s = "MCMXCIV" — every one of its three subtractive pairs (CM, XC, IV) is resolved as (current < next) → subtract:
scan pointer reads the current symbol; the one to its right is compared — subtrahends discount their bigger neighbor, adds carry it
The whole trick lives in the SUBTRACTIVE PAIR rule: scan left to right, and a symbol whose value is strictly smaller than the NEXT symbol is subtracted, otherwise it is added. Only I, X and C ever play the small subtractive role, and each only sits before a specific bigger neighbor (I before V or X, X before L or C, C before D or M). MCMXCIV exercises three of those six pairings, so it is the perfect test drive: read it as M + CM + XC + IV.
Then the add-only side, s = "LVIII" — note how the run of equal Is still adds, because the rule compares with a strict less-than:
scan pointer reads the current symbol; the one to its right is compared — subtrahends discount their bigger neighbor, adds carry it
LVIII shows the ADD-only side of the rule. L is 50, V is 5, and the three I are each 1. No symbol here is followed by a strictly bigger one, so nothing ever subtracts and the total is a plain running sum. The subtle case to watch is the run of equal I: equal neighbors STILL add.
Why it is linear: each of the n symbols is read exactly once and does a single O(1) comparison against one neighbor, giving O(n) time — the same asymptotic class as the brute force but with a suffix-scan per position replaced by one neighbor check. This is optimal: every symbol must be read at least once to know its value, so no algorithm can beat O(n). Space is O(1) beyond the fixed seven-entry lookup table.