Roman to Integer

Description

13. Roman to Integer

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

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Roman numerals are usually written largest to smallest from left to right. However, six instances use subtraction:

• I before V (5) and X (10) makes 4 and 9.
• X before L (50) and C (100) makes 40 and 90.
• C before D (500) and M (1000) makes 400 and 900.

Given a roman numeral string s, convert it to an integer.

Example 1:
Input: s = "III"
Output: 3

Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V = 5, III = 3.

Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

• $1\le \text{s.length}\le 15$
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range $[1,3999]$.

---

Approach 1: Left-to-Right Comparison ($O(N)$ Time, $O(1)$ Space)

Intuition

Iterate through the string from left to right. Look ahead to the next character:

• If the current character value is less than the next character value (e.g., IV where $1<5$), subtract the current value from the total sum.
• Otherwise, add the current value to the total sum.

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
 
        int total = 0;
        int n = s.length();
 
        for (int i = 0; i < n; i++) {
            int current = map.get(s.charAt(i));
            
            // If current symbol is smaller than the next symbol, subtract it
            if (i < n - 1 && current < map.get(s.charAt(i + 1))) {
                total -= current;
            } else {
                total += current;
            }
        }
 
        return total;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Single pass over the string of length $N$ (where $N\le 15$).
• Space Complexity: $O(1)$ — The map size is fixed at 7 entries.

---

Approach 2: Right-to-Left Traversal with switch (Most Optimized — $O(N)$ Time, $O(1)$ Space)

Intuition

Iterate backwards from the end of the string while maintaining a prev variable to store the value of the last seen character:

• If current < prev, we are in a subtraction pair (e.g., I before V), so subtract current from total.
• If current >= prev, add current to total.

Using a helper function with switch instead of a HashMap avoids object creation and lookup overhead.

class Solution {
    public int romanToInt(String s) {
        int total = 0;
        int prev = 0;
 
        // Traverse backwards
        for (int i = s.length() - 1; i >= 0; i--) {
            int current = getValue(s.charAt(i));
 
            if (current < prev) {
                total -= current;
            } else {
                total += current;
            }
            prev = current;
        }
 
        return total;
    }
 
    private int getValue(char ch) {
        switch (ch) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Single reverse traversal over $N$ characters.
• Space Complexity: $O(1)$ — Uses primitive integer variables with zero extra memory allocation.

---

Easy Memory Rule

“Traverse backwards: if the current value is smaller than the previous value, SUBTRACT it; otherwise, ADD it.”