13. Roman to Integer

EasyHash TableMathString
Leetcode Link

Problem Description

Roman numerals are a numeral system from ancient Rome based on combinations of letters from the Latin alphabet (I, V, X, L, C, D, M) to represent numbers. Each symbol has a fixed numerical value, with I equal to 1, V equal to 5, X equal to 10, L equal to 50, C equal to 100, D equal to 500, and M equal to 1000. Numbers in Roman numerals are formed by combining these symbols and adding up their values. However, when a smaller numeral comes before a larger one, this indicates that the smaller numeral should be subtracted from the larger numeral instead of added (for example, IV means 4, not 6). This rule is used in six instances: I before V and X, X before L and C, and C before D and M. The task is to convert a string representing a Roman numeral into the integer it represents.

Intuition

To solve the problem, we should first create a mapping of Roman numeral symbols to their respective integer values. This allows for easy lookup during the conversion. To convert the Roman numeral to an integer, we can iterate over the string from left to right, checking the value of each symbol in comparison to the symbol to its right.

If a symbol is followed by one of greater value, it means we need to subtract the value of the current symbol from our result. Otherwise, we can simply add the value of the symbol. This adheres to the subtraction rule given for cases like IV or IX. To implement this in Python, we can take advantage of the pairwise utility from the itertools module, which will give us each symbol and the one following it. If the module itertools is not available or if pairwise is not a part of itertools, we can use a simple 'zip' technique to iterate through the symbol pairs. Then, we just need to add the value of the last symbol at the end since it's not included in these pairwise comparisons.

The algorithm is relatively straightforward: we initialize a sum to 0 and iterate the symbols pairwise (current and next symbol). If the current is less than the next one, we subtract its value from the sum. If the current is greater than or equal to the next one, we add its value to the sum. After the loop, we catch the edge case by including the last symbol's value, since it's always added to the total.

Learn more about Math patterns.

Solution Approach

The solution involves a straightforward process which utilizes a hash table and a simulation algorithm based on the rules of Roman numerals.

  1. We define a hash table (in Python, a dictionary) d which maps each Roman numeral symbol to its integer value. The key-value pairs in this dictionary are as follows: 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, and 'M': 1000.

  2. To convert a Roman numeral string to an integer, we iterate over the string one character at a time, examining the symbol and the one that follows it (this is the pairwise comparison). For this task, we use a for loop in conjunction with the Python generator expression format. To demonstrate, we generate tuples of (current character a, next character b) using the pairwise utility or a manual method by zipping the string with itself offset by one character.

  3. In this iteration, we compare the integer value of the current symbol with the value of the symbol following it. If the current value is less than the next, we should deduct its value from the total sum since it indicates subtraction as per Roman numerals (e.g., IV for 4). If the current value is equal to or greater than the following symbol's value, we add it to the total sum.

  4. The comparison (d[a] < d[b]) returns a boolean, and in the solution, it is used to determine whether the value will be subtracted -1 * d[a] or added 1 * d[a]. We use a sum function to add all these values together.

  5. As the pairwise comparison does not include the very last symbol in the computation, we correct for this by adding d[s[-1]] to the total sum to include the value of the last symbol.

  6. The final sum that results from this process is the integer value of the provided Roman numeral string.

To demonstrate the implementation of our approach with the code:

1class Solution:
2    def romanToInt(self, s: str) -> int:
3        d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
4        total = sum((-1 if d[a] < d[b] else 1) * d[a] for a, b in pairwise(s)) + d[s[-1]]
5        return total

In the above code, pairwise(s) would need to be replaced by an equivalent if it's not available in the standard Python library: zip(s, s[1:]). Here, zip pairs each character with the next, effectively creating the needed pairwise functionality.

1# If pairwise is not inbuilt, we can define our own pairwise function like this:
2from itertools import tee
3
4def pairwise(iterable):
5    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
6    a, b = tee(iterable)
7    next(b, None)
8    return zip(a, b)
9
10# Alternatively, we can modify the loop in the main function to not need pairwise:
11class Solution:
12    def romanToInt(self, s: str) -> int:
13        d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
14        total, prev_value = 0, 0
15        for char in reversed(s):
16            if d[char] < prev_value:
17                total -= d[char]
18            else:
19                total += d[char]
20            prev_value = d[char]
21        return total

By adapting the algorithm to avoid using the pairwise utility, we ensure compatibility with the Python standard library without relying on any external or updated modules.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Example Walkthrough

Let's use the Roman numeral MCMIV as an example to illustrate the solution approach, which translates to 1904 in integer form. This number is chosen because it includes subtraction instances (CM and IV).

Following the solution approach steps:

  1. We create a dictionary called d that maps each Roman numeral to its integer value:

    1d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
  2. We start iterating over the Roman numeral string "MCMIV" using pairs:

    • Pair MC (M=1000, C=100)
    • Pair CM (C=100, M=1000)
    • Pair MI (M=1000, I=1)
    • Pair IV (I=1, V=5)
  3. We compare the values of each pair:

    • For MC, 1000 is greater than 100, so we add 1000.
    • For CM, 100 is less than 1000, so we subtract 100.
    • For MI, 1000 is greater than 1, so we add 1000.
    • For IV, 1 is less than 5, so we subtract 1.
  4. We perform the addition and subtraction as directed:

    • Starting sum is 0.
    • Add M (1000) = 1000.
    • Subtract C (100) from sum (900).
    • Add M (1000) to sum (1900).
    • Subtract I (1) from sum (1899).
  5. We add the last character value (V=5) to the sum since the pairwise comparison above doesn't account for it:

    • The final sum is 1899 + 5 = 1904, which is the integer equivalent of "MCMIV".

This methodically breaks down the input string, using the subtraction rule as needed, and continues to accumulate the total to reach the correct conversion from Roman numeral to integer.

Solution Implementation

1class Solution:
2    def romanToInt(self, s: str) -> int:
3        # Create a dictionary mapping Roman numerals to integers.
4        roman_to_int = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
5      
6        # Initialize the previous number with the value of the last Roman numeral.
7        previous_number = roman_to_int[s[-1]]
8      
9        # Initialize the total with the value of the last Roman numeral.
10        total = previous_number
11      
12        # Loop over the string of Roman numerals in reverse order (right-to-left).
13        for i in range(len(s) - 2, -1, -1):
14            # Get the integer value of the current Roman numeral.
15            current_number = roman_to_int[s[i]]
16          
17            # If the current value is less than the previous value, we need to subtract it.
18            # Otherwise, we add it.
19            if current_number < previous_number:
20                total -= current_number
21            else:
22                total += current_number
23          
24            # Update the previous number for the next iteration.
25            previous_number = current_number
26      
27        # Return the computed total, which is the integer equivalent of the Roman numeral string.
28        return total
29
30# Example use:
31# solution = Solution()
32# result = solution.romanToInt("MCMXCIV")
33# print(result)  # Output: 1994
34
1class Solution {
2    public int romanToInt(String s) {
3        // A string representing the Roman numerals in increasing order.
4        String romanSymbols = "IVXLCDM";
5        // Corresponding values of Roman numerals as per the order in the string.
6        int[] values = {1, 5, 10, 50, 100, 500, 1000};
7        // Map to store Roman numerals and their values for quick access.
8        Map<Character, Integer> numeralToValue = new HashMap<>();
9      
10        // Populate the map with symbol-value pairs.
11        for (int i = 0; i < values.length; ++i) {
12            numeralToValue.put(romanSymbols.charAt(i), values[i]);
13        }
14      
15        // Length of the string containing the Roman numeral.
16        int length = s.length();
17        // Start with the value of the last symbol as there is nothing following it to compare.
18        int totalValue = numeralToValue.get(s.charAt(length - 1));
19      
20        // Loop through the string in reverse order stopping before the first character.
21        for (int i = 0; i < length - 1; ++i) {
22            // Determine the sign based on whether the current symbol is less than the one following it.
23            // This helps in applying the subtractive rule of Roman numerals.
24            int sign = numeralToValue.get(s.charAt(i)) < numeralToValue.get(s.charAt(i + 1)) ? -1 : 1;
25            // Add or subtract the value of the current symbol to the total value.
26            totalValue += sign * numeralToValue.get(s.charAt(i));
27        }
28      
29        // Return the computed total value as the integer value of the input Roman numeral.
30        return totalValue;
31    }
32}
33
1#include <unordered_map>
2#include <string>
3
4class Solution {
5public:
6    // Function to convert a Roman numeral to an integer.
7    int romanToInt(std::string s) {
8        // Map to store the Roman numerals and their corresponding integer values.
9        std::unordered_map<char, int> numeralToValue{
10            {'I', 1},
11            {'V', 5},
12            {'X', 10},
13            {'L', 50},
14            {'C', 100},
15            {'D', 500},
16            {'M', 1000},
17        };
18
19        // Start by adding the value of the last character to the answer.
20        int total = numeralToValue[s.back()];
21
22        // Iterate over the string from the start to the second-to-last character.
23        for (int i = 0; i < s.size() - 1; ++i) {
24            // Determine the sign of the value based on the following numeral in the sequence.
25            // If the current numeral is less than the next one, it should be subtracted.
26            int sign = numeralToValue[s[i]] < numeralToValue[s[i + 1]] ? -1 : 1;
27          
28            // Add the current numeral's value to the total, adjusting the sign as necessary.
29            total += sign * numeralToValue[s[i]];
30        }
31
32        // Return the computed integer value of the Roman numeral string.
33        return total;
34    }
35};
36
1// Function to convert a Roman numeral string to an integer.
2function romanToInt(s: string): number {
3    // A map representing the Roman numeral characters and their integer values.
4    const romanToValue: Map<string, number> = new Map([
5        ['I', 1],
6        ['V', 5],
7        ['X', 10],
8        ['L', 50],
9        ['C', 100],
10        ['D', 500],
11        ['M', 1000],
12    ]);
13
14    // Initialize the result with the integer value of the last Roman numeral character.
15    let result: number = romanToValue.get(s[s.length - 1])!;
16  
17    // Iterate over the string (excluding the last character) to calculate the total value.
18    for (let i = 0; i < s.length - 1; ++i) {
19        // Determine the sign: -1 if the current Roman numeral is less than the one after it, else 1.
20        const sign: number = romanToValue.get(s[i])! < romanToValue.get(s[i + 1])! ? -1 : 1;
21      
22        // Add the current Roman numeral's value times the determined sign to the result.
23        result += sign * romanToValue.get(s[i])!;
24    }
25
26    // Return the final integer result.
27    return result;
28}
29

Time and Space Complexity

The time complexity of the given code can be analyzed based on the operations performed on the input string s. The function iterates over pairs of adjacent characters in the string, which is done by pairwise(s). Since pairwise essentially goes through the entire string once to create these pairs, the number of operations will be proportional to the length of the string n. Therefore, the time complexity is O(n).

In terms of space complexity, the auxiliary space used by the algorithm is for the dictionary d that stores the Roman numerals and their corresponding integer values. The size of d is constant, as there are a fixed number of Roman numerals. However, pairwise(s) generates an iterator which does not store all pairs in memory at once, hence it does not add to the space complexity. Therefore, the space complexity remains constant, not dependent on the length of the input string, and can be denoted as O(1), rather than O(m), since m would imply a dependency on the size of the character set that isn't present here.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄