13. Roman to Integer

Scan left to right, adding each symbol's value — but when a smaller symbol sits directly before a larger one, it's a subtractive pair (like IV = 4), so subtract it instead of adding.

Idea

Roman numerals are almost purely additive: XII = 10 + 1 + 1. The only wrinkle is the six subtractive pairs (IV, IX, XL, XC, CD, CM). There's a clean rule that captures all of them without special-casing: a symbol is subtracted exactly when the symbol immediately to its right is larger.

Algorithm

1. Map each symbol to its value.
2. Walk the string. For symbol i: if i+1 exists and value[s[i]] < value[s[i+1]], subtract value[s[i]]; otherwise add it.
3. Return the running total.

Worked example: "MCMXCIV"

Result: 1994.

Complexity

• Time: O(n) — one pass.
• Space: O(1) — a fixed symbol table.

import java.util.Map;

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> values = Map.of(
            'I', 1, 'V', 5, 'X', 10, 'L', 50,
            'C', 100, 'D', 500, 'M', 1000
        );
        int total = 0;
        for (int i = 0; i < s.length(); i++) {
            int cur = values.get(s.charAt(i));
            if (i + 1 < s.length() && cur < values.get(s.charAt(i + 1))) {
                total -= cur;
            } else {
                total += cur;
            }
        }
        return total;
    }
}