Roman to Integer - Solution & Explanation

Problem Overview: Roman numerals represent numbers using characters like I, V, X, L, C, D, and M. Each symbol has a value, but smaller symbols placed before larger ones indicate subtraction (e.g., IV = 4). The task is to convert a Roman numeral string into its integer value while correctly handling these subtractive patterns.

Approach 1: Linear Scan from Left to Right (O(n) time, O(1) space)

Store the value of each Roman symbol in a small lookup structure such as a hash table. Iterate through the string from left to right. For each character, compare its value with the value of the next character. If the current value is smaller than the next one, subtract it from the total because this represents a subtractive pair (for example, I before V). Otherwise, add the value normally. This approach directly models how Roman numerals are written and keeps the logic simple. The iteration touches each character once, giving O(n) time complexity, while the lookup map and a few variables keep space at O(1).

This method is intuitive and mirrors the rules of Roman numerals closely. Many candidates start with this approach because it clearly expresses the subtractive rule and is easy to debug during interviews.

Approach 2: Optimized Reverse Iteration (O(n) time, O(1) space)

Instead of checking the next symbol, iterate from right to left. Maintain the value of the previous numeral seen during the traversal. For each symbol, look up its value from the same mapping structure (again typically implemented with a hash table). If the current value is smaller than the previous value, subtract it from the total. Otherwise, add it and update the previous value.

The key insight is that Roman numerals only subtract when a smaller symbol appears before a larger one. When scanning from the end, the "previous" value naturally represents the larger numeral in those cases. This eliminates the need to check the next character or manage index bounds. The algorithm still performs a single pass over the string, so the time complexity remains O(n) and space stays O(1). Many engineers prefer this version because the subtraction rule becomes a simple comparison with the last processed value.

Recommended for interviews: Both approaches are linear and acceptable. Interviewers typically expect the reverse-iteration solution because the logic is cleaner and avoids look‑ahead checks. Starting with the left‑to‑right scan demonstrates that you understand Roman numeral subtraction rules, then refining it to the reverse traversal shows strong algorithmic thinking. The core idea in both implementations is constant-time value lookup combined with a single pass over the input using basic math comparisons.