Problem

Roman numerals

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Examples

Example 1:

1
2
3

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

1
2
3

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

Example 3:

1
2
3

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

Solution

Method 1 - Using Hashtable Greedily

The primary challenge in counting Roman numerals arises when a numeral acts as a subtractive value rather than an additive one. For instance, in “IV”, the value of “I” (1) is subtracted from the value of “V” (5). Apart from these cases, you simply sum the values of all the numerals.

Subtractive numerals can be recognized because they appear before a larger numeral. To handle this, we track two variables: prev and curr. For IV, prev is I and curr is V. When prev is less than curr, we subtract prev. After this, we continue by adding prev.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

public int romanToInt(String s) {
    // If the input string is null or empty, return 0
    if (s == null || s.length() == 0) {
        return 0;
    }

    // Create a map to store Roman numeral symbols and their integer values
    Map<Character, Integer> map = Map.of(
        'M', 1000,
        'D', 500,
        'C', 100,
        'L', 50,
        'X', 10,
        'V', 5,
        'I', 1
    );

    // Initialize sum to store the final integer value
    int sum = 0;
    // Initialize prev to store the value of the first Roman numeral
    int prev = map.get(s.charAt(0));
    // Initialize curr to store the value of the current Roman numeral
    int curr = 0;

    // Iterate over the string starting from the second character
    for (int i = 1; i < s.length(); i++) {
        // Get the value of the current Roman numeral
        curr = map.get(s.charAt(i));

        // If prev is less than curr, subtract prev from sum to handle the subtraction case
        if (prev < curr) {
            sum -= prev;
        } else {
            // Otherwise, add prev to sum
            sum += prev;
        }

        // Update prev to the value of the current Roman numeral
        prev = curr;
    }

    // Add the last processed Roman numeral value to sum
    // This takes care of adding the last numeral which was not included in the loop
    sum += prev;

    // Return the final calculated integer value
    return sum;
}
 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

def romanToInt(s: str) -> int:
    # If the input string is empty, return 0
    if not s:
        return 0

    # Create a dictionary to store Roman numeral symbols and their integer values
    roman_map = {
        'M': 1000,
        'D': 500,
        'C': 100,
        'L': 50,
        'X': 10,
        'V': 5,
        'I': 1
    }

    # Initialize sum to store the final integer value
    sum = 0
    # Initialize prev to store the value of the first Roman numeral
    prev = roman_map[s[0]]

    # Iterate over the string starting from the second character
    for i in range(1, len(s)):
        # Get the value of the current Roman numeral
        curr = roman_map[s[i]]

        # If prev is less than curr, subtract prev from sum to handle the subtraction case
        if prev < curr:
            sum -= prev
        else:
            # Otherwise, add prev to sum
            sum += prev

        # Update prev to the value of the current Roman numeral
        prev = curr

    # Add the last processed Roman numeral value to sum
    # This takes care of adding the last numeral which was not included in the loop
    sum += prev

    # Return the final calculated integer value
    return sum

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1) as we are storing 7 values in map