Roman to Integer

Problem Link

13. Roman to Integer – LeetCode

Problem Statement

Convert a Roman numeral string into its corresponding integer value.

Roman numerals are written by combining letters representing values:

Certain combinations involve subtraction when a smaller value precedes a larger one:

• I before V or X → 4 or 9

• X before L or C → 40 or 90

• C before D or M → 400 or 900

Examples

Example 1:

Input: s = "III"
Output: 3
Explanation: 1 + 1 + 1 = 3

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: 50 + 5 + 3 = 58

Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: 1000 + 900 + 90 + 4 = 1994

Constraints

• 1 <= s.length <= 15

• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M')

• It is guaranteed to be a valid Roman numeral in standard format.

Intuition

We move left to right, converting characters using a Map.

Normally, we add each character's value.

But if a smaller value comes before a larger one (like I before V), we need to subtract it instead.

Approach

1. Create a mapping of Roman symbols to integer values.

2. Initialize result as 0.

3. Iterate through the string from left to right:

   • If the current value is less than the next value → subtract

   • Else → add

4. Return the result.

Java Code

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 res = 0;
        for (int i = 0; i < s.length(); i++) {
            int val = map.get(s.charAt(i));
            if (i + 1 < s.length() && val < map.get(s.charAt(i + 1))) {
                res -= val;
            } else {
                res += val;
            }
        }
        return res;
    }
}

Time and Space Complexity

Dry Run

Input: "MCMXCIV"

Final result: 1994

Conclusion

This is a great example of a greedy approach using a hash map for Roman numeral decoding. The key trick is:

• If current < next, subtract current

• Else, add current

You can also extend this pattern for integer to Roman conversion or other numeral systems.