Algorithm Day108 - Roman to Integer

Posted on In Views:

📌 Problem

Convert a Roman numeral to an integer. Input is guaranteed to be within the range corresponding to standard Roman numerals (typically 1..3999).

Roman numerals are represented by the symbols:
I(1), V(5), X(10), L(50), C(100), D(500), M(1000).
Some symbols may be placed before larger symbols to indicate subtraction, e.g., IV = 4, IX = 9.

💬 Examples

Example 1

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

Example 2

1
2
Input: s = "IV"
Output: 4

Example 3

1
2
Input: s = "MCMXCIV"
Output: 1994

💡 Intuition (Greedy / Left-to-right)

Scan from left to right, adding values. If a smaller-value symbol appears before a larger one, subtract the smaller; otherwise add it. A simple approach: for each character, compare its value with the next character (if any) to decide add or subtract.

🔢 Java Code (Map + Greedy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;

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

⏱ Complexity Analysis

  • Time: O(n) — single pass over the string.
  • Space: O(1) — constant-size map and a few variables.

✍️ Summary

  • Use a mapping from Roman symbols to integers.
  • Subtract when a smaller symbol precedes a larger one; otherwise add.
  • Simple, linear-time solution ideal for interviews.