Roman to Integer

Easy

Adobe

0 views

Topics:

StringsArrays

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

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 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 <= s.length <= 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].

Roman to Integer

Easy

Adobe

0 views

Topics:

StringsArrays

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

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 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 <= s.length <= 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].

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the valid range for the input Roman numeral string's length?
Can I assume the input string will only contain valid Roman numeral characters (I, V, X, L, C, D, M)?
Is the input Roman numeral guaranteed to be a valid Roman numeral string, or do I need to handle invalid formats?
What is the expected range for the integer value the Roman numeral represents?
Should I handle an empty input string, and if so, what should I return?

Brute Force Solution

Approach

The brute force way to convert a Roman numeral to a number involves checking the value of each Roman symbol and combining them. It's like looking up each letter in a dictionary and adding up their values according to some basic rules, trying every possible combination until you have a total value.

Here's how the algorithm would work step-by-step:

Start by looking at the Roman numeral from left to right, one symbol at a time.
For each symbol, find its corresponding value (e.g., I is 1, V is 5, X is 10, and so on).
If the current symbol's value is greater than or equal to the next symbol's value, simply add its value to the total.
If the current symbol's value is less than the next symbol's value, subtract its value from the next symbol's value, and add that result to the total. Then, skip the next symbol because it has already been considered.
Keep doing this for all the symbols in the Roman numeral.
The final total is the integer representation of the Roman numeral.

Code Implementation

def roman_to_integer(roman_string):
    roman_values = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    }
    total_value = 0
    index = 0

    while index < len(roman_string):
        current_value = roman_values[roman_string[index]]

        # Need to check if next index exists
        if index + 1 < len(roman_string):
            next_value = roman_values[roman_string[index + 1]]

            # Subtractive case
            if current_value < next_value:
                total_value += next_value - current_value

                # Skip the next symbol since it was processed
                index += 2

            else:
                # Additive case, current >= next
                total_value += current_value
                index += 1

        else:
            # Last roman letter, just add to total
            total_value += current_value
            index += 1

    return total_value

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input Roman numeral string of length n from left to right, examining each symbol once. In each iteration, it performs a constant amount of work: looking up the symbol's value and comparing it with the next symbol (if it exists). Even when a subtraction is performed, only two symbols are involved. Therefore, the time complexity is directly proportional to the length of the input string, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm described only uses a few constant space variables to store the current symbol's value, the next symbol's value, and the running total. The amount of memory used does not scale with the input string's length (N). Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The efficient way to convert Roman numerals to integers recognizes that Roman numerals are generally written largest to smallest, but with a key exception for subtractive pairs like IV or IX. We can solve this by iterating through the numeral string and tracking the value of each symbol, subtracting when we encounter a smaller value before a larger one.

Here's how the algorithm would work step-by-step:

Create a way to look up the integer value of each Roman numeral symbol (like I, V, X, L, C, D, M).
Start at the beginning of the Roman numeral string.
Look at the current symbol and the symbol immediately to its right.
If the current symbol's value is less than the next symbol's value (like 'I' before 'V'), subtract the current symbol's value from the total.
Otherwise (if the current symbol's value is greater than or equal to the next symbol's value, or if it's the last symbol), add the current symbol's value to the total.
Move to the next symbol in the string and repeat the process until you reach the end.
The final total will be the integer value of the Roman numeral.

Code Implementation

def roman_to_integer(roman_string):
    roman_values = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    integer_value = 0
    previous_value = 0

    # Iterate through the Roman numeral string from left to right
    for i in range(len(roman_string)):
        current_value = roman_values[roman_string[i]]

        # Handle subtractive cases (e.g., IV, IX)
        if current_value > previous_value and i > 0:
            # Subtract twice the previous value because it was added before
            integer_value += current_value - 2 * previous_value

        # Handle additive cases
        else:
            integer_value += current_value

        previous_value = current_value

    return integer_value

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the Roman numeral string of length n only once. In each iteration, it performs a constant number of operations: looking up the values of the current and next Roman numerals, comparing them, and adding or subtracting from the total. Since the number of operations is directly proportional to the length of the input string, the time complexity is O(n).

Space Complexity

O(1) – The space complexity is O(1) because the algorithm uses a fixed amount of extra memory regardless of the input Roman numeral string's length (N). The plain English description mentions creating a lookup for Roman numeral values, which typically involves a fixed-size hash map or dictionary (e.g., {'I': 1, 'V': 5, ...}). The algorithm also uses a few constant space variables to store the current symbol's value, the next symbol's value, and the running total, all independent of N. Therefore, the auxiliary space remains constant.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 immediately as there is no Roman numeral to convert.
Invalid Roman numeral characters (e.g., 'A', 'Z')	Either throw an IllegalArgumentException or define a behavior, such as returning 0, to handle unrecognized input characters.
Roman numeral with invalid ordering (e.g., 'IIII', 'VX')	The solution must correctly handle subtraction rules, and may need to either throw an exception or return 0 if the ordering is illegal.
Maximum possible valid Roman numeral (e.g., 'MMMCMXCIX' which is 3999)	Ensure the resulting integer does not exceed the maximum integer value the programming language supports, or handle potential overflow if possible.
Input string with leading/trailing whitespace	Trim the input string to remove leading and trailing whitespaces before processing to ensure correct conversion.
Single character Roman numeral (e.g., 'I', 'V', 'X', 'L', 'C', 'D', 'M')	The algorithm should directly return the corresponding integer value of the single character.
Roman numeral with repeated subtractive pairs (e.g., 'IXIX')	The solution must be able to identify and reject this invalid pattern, and should either throw an exception or return 0.
Very long Roman numeral string near allowed length limit	Verify that the solution handles the performance for relatively large input strings without excessive time complexity and within memory constraints.