1. Understanding the Problem

Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M.

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + I + I. 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.

The Subtraction Rules (The Core Trick):

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 string s, your task is to convert it to an integer.

2. The Naive Approach: String Replace

The most intuitive, brute-force way to handle subtraction cases is to eliminate them beforehand. You search for all six special pairs ("IV", "IX", "XL", "XC", "CD", "CM") in the string and replace them with alternative placeholders (or manually add their combined values and remove them from the string).

Trade-off Analysis

While this logic works, it is unnecessarily messy and inefficient:

• Time Complexity: O(N) — Though linear, string allocation and multi-pass replacement functions create overhead.
• Space Complexity: O(N) — Creating modified copy strings wastes extra memory allocations.

3. The Optimal Approach: Lookahead Traversal (O(N) Time, O(1) Space)

To pass a senior-level technical interview, we want to achieve a clean single-pass O(N) time complexity with strictly O(1) auxiliary space.

Instead of pre-replacing strings, we can map each symbol to its value using a small lookup dictionary or switch statement. As we iterate left to right, we compare the value of the current character with the next character:

• If current_val < next_val: This is a subtraction case (like IV where 1 < 5). We subtract current_val from our running total.
• If current_val >= next_val: This is a standard addition case (like VI where 5 > 1). We add current_val to our running total.

This single observation completely unifies the logic, seamlessly handling both standard additions and all subtraction edge cases without any multi-character string replacing!

4. The Logic Step-by-Step

1. Build the Lookup Map: Store the basic symbol-to-value mappings in a hash table or fixed array.
2. Initialize total = 0 to hold the final sum.
3. Iterate Through String: Loop through each character index i from 0 to len(s) - 1:
   • Check if i + 1 < len(s) and values[s[i]] < values[s[i+1]].
   • If True: We encountered a subtraction case (e.g., 'I' before 'V'). Subtract values[s[i]] from total.
   • If False: Standard case. Add values[s[i]] to total.
4. Return total.

5. Complexity Analysis

• Time Complexity: O(N) — We scan through the string of length N exactly once. Hash map / character lookups take O(1) time.
• Space Complexity: O(1) — The lookup table contains a fixed set of 7 key-value pairs. Memory usage remains strictly constant regardless of input length.

6. Code Implementations

Expand the sections below to see the optimal O(1) space "Lookahead Traversal" implementations across different languages.

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_map = {
            'I': 1, 'V': 5, 'X': 10, 'L': 50,
            'C': 100, 'D': 500, 'M': 1000
        }
        
        total = 0
        n = len(s)
        
        for i in range(n):
            # If current symbol is smaller than the next symbol, subtract it
            if i + 1 < n and roman_map[s[i]] < roman_map[s[i + 1]]:
                total -= roman_map[s[i]]
            else:
                total += roman_map[s[i]]
                
        return total

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> romanMap = new HashMap<>();
        romanMap.put('I', 1);
        romanMap.put('V', 5);
        romanMap.put('X', 10);
        romanMap.put('L', 50);
        romanMap.put('C', 100);
        romanMap.put('D', 500);
        romanMap.put('M', 1000);
        
        int total = 0;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            int currentVal = romanMap.get(s.charAt(i));
            
            // Subtraction check: compare current value with next value
            if (i + 1 < n && currentVal < romanMap.get(s.charAt(i + 1))) {
                total -= currentVal;
            } else {
                total += currentVal;
            }
        }
        
        return total;
    }
}

#include <string>
#include <unordered_map>

class Solution {
public:
    int romanToInt(std::string s) {
        std::unordered_map<char, int> romanMap = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
            {'C', 100}, {'D', 500}, {'M', 1000}
        };
        
        int total = 0;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            // Compare current symbol value with the next one
            if (i + 1 < n && romanMap[s[i]] < romanMap[s[i + 1]]) {
                total -= romanMap[s[i]];
            } else {
                total += romanMap[s[i]];
            }
        }
        
        return total;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just mastered the "Roman to Integer" conversion pattern! The key takeaway from this problem is discovering the unifying mathematical rule: when reading symbols, a smaller value before a larger value implies subtraction. By leveraging a single lookahead comparison (current < next), you converted what could have been a tedious set of multi-character if-else conditions into an elegant, single-pass O(N) solution. Keep this lookahead technique in your mental toolkit, as it is the exact foundation for custom parser and tokenizer interview questions!