Roman to Integer

#2 Most AskedEasy

Roman to Integer #2 Most Asked

Easy

AMD

45 views

Topics:

Strings

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].

Try coding it in LeetCode

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 guaranteed range of the input Roman numeral string 's' (e.g., minimum and maximum length, and if it's guaranteed to be a valid Roman numeral)?
Are there any specific symbols or combinations of symbols that are considered invalid or outside the scope of standard Roman numeral representation that I should handle?
Is it possible for the input string to be empty or null, and if so, what should be the expected output in those cases?
What is the maximum integer value that a valid Roman numeral string can represent? This will help me consider potential integer overflow issues, although less likely with standard Roman numerals.
Are we dealing with standard Roman numeral rules (e.g., 'IIII' is not allowed, only 'IV' for 4), or are there any variations in the rules to consider?

Brute Force Solution

Approach

To convert a Roman numeral to an integer using a brute force approach, we can think of it as systematically processing the Roman numeral string from left to right, character by character, and accumulating the corresponding integer value.

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

Start with a total value of zero.
Look at the first character of the Roman numeral.
If it's an 'I', add one to the total.
If it's a 'V', add five to the total.
If it's an 'X', add ten to the total.
If it's an 'L', add fifty to the total.
If it's a 'C', add one hundred to the total.
If it's a 'D', add five hundred to the total.
If it's an 'M', add one thousand to the total.
Now, consider the next character. If this character represents a larger value than the previous one, it means we have a subtractive case (like 'IV' meaning four). In this situation, instead of adding the value of the current character, we actually need to subtract the value of the previous character twice and then add the value of the current character.
For example, if we just added one for 'I' and the next character is 'V', we would undo the addition of one (making the total zero again) and then add five, resulting in a total of four.
Continue this process for every character in the Roman numeral, always considering the relationship between the current character and the one immediately before it.
After processing all the characters, the final accumulated total will be the integer representation of the Roman numeral.

Code Implementation

def roman_to_integer_brute_force(roman_numeral_string):    total_integer_value = 0    roman_map = {        'I': 1,        'V': 5,        'X': 10,        'L': 50,        'C': 100,        'D': 500,        'M': 1000    }    for current_index in range(len(roman_numeral_string)):        current_roman_value = roman_map[roman_numeral_string[current_index]]        # If this is not the last character, check if the next character has a larger value        if current_index < len(roman_numeral_string) - 1:            next_roman_value = roman_map[roman_numeral_string[current_index + 1]]            # If the next value is greater, we have a subtractive case            if next_roman_value > current_roman_value:                # We need to subtract the current value twice and then add the next value                # This effectively means we are adding the difference (next_roman_value - current_roman_value)                total_integer_value -= current_roman_value                # Add the current character's value to the total        total_integer_value += current_roman_value    return total_integer_value

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the Roman numeral string once, character by character. For each character, it performs a constant number of operations: checking its value and comparing it with the previous character's value. If n is the length of the Roman numeral string, the total number of operations is directly proportional to n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The described brute-force approach uses a constant amount of extra space. A single variable is used to store the 'total value', and another variable (implicitly) to keep track of the 'previous character's value' for subtractive cases. The space used does not depend on the length of the Roman numeral string (N) and remains fixed regardless of the input size.

Optimal Solution

Approach

The key is to process the Roman numeral from right to left, which simplifies handling the subtractive rule. By comparing each numeral to the one immediately to its right, we can determine whether to add or subtract its value.

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

Imagine you have a little machine that can translate Roman numerals. To make it work efficiently, you'll start reading the numeral from the very end, moving backwards.
As you look at each Roman numeral symbol, compare its value to the value of the symbol that comes right before it (which you've already looked at).
If the current symbol's value is smaller than the one before it, it means we need to subtract this current symbol's value from our running total.
If the current symbol's value is greater than or equal to the one before it, we simply add its value to our running total.
Keep doing this for every symbol, moving from right to left, and the final running total will be the integer representation of the Roman numeral.
This right-to-left approach cleverly handles cases like 'IV' (4) or 'IX' (9) without needing special checks.

Code Implementation

def roman_to_integer(roman_numeral_string):    roman_value_map = {        'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000    }    total_integer_value = 0    previous_symbol_value = 0    # Iterate from right to left to handle subtractive cases easily.    for current_symbol in reversed(roman_numeral_string):        current_symbol_value = roman_value_map[current_symbol]        # If the current symbol's value is less than the previous one, subtract it.        if current_symbol_value < previous_symbol_value:            total_integer_value -= current_symbol_value        else:            # Otherwise, add the current symbol's value to the total.            total_integer_value += current_symbol_value        # Update the previous symbol's value for the next iteration.        previous_symbol_value = current_symbol_value    return total_integer_value

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the Roman numeral string exactly once, from right to left. For each Roman numeral character, a constant time lookup is performed to get its integer value, and a constant time comparison and addition/subtraction operation is done. Therefore, if 'n' is the length of the Roman numeral string, the total number of operations is directly proportional to 'n', resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm primarily uses a single variable to maintain the running total and another variable to store the value of the previously processed Roman numeral. There are no auxiliary data structures that grow with the input string's length (N). The memory footprint remains constant regardless of the length of the Roman numeral string.

Edge Cases

Case	How to Handle
Null or empty input string	The solution should return 0 for a null or empty input string, as there are no Roman numerals to convert.
Single character Roman numeral (e.g., 'I', 'V')	The solution should correctly map single characters to their corresponding integer values.
Roman numerals with subtractive notation (e.g., 'IV', 'IX', 'XL', 'XC', 'CD', 'CM')	The algorithm must be designed to handle these specific combinations by checking preceding characters.
Roman numerals with repeated characters (e.g., 'III', 'XX')	The solution should correctly sum the values of repeated characters.
Longest possible valid Roman numeral input	The solution should scale efficiently for longer strings, ensuring performance does not degrade significantly.
Invalid Roman numeral characters (e.g., 'A', 'Z', numbers)	The problem statement implies valid Roman numeral input; however, a robust solution might throw an error or return a specific indicator for invalid characters.
Roman numerals exceeding the standard representation (e.g., 'MMMM')	The standard Roman numeral system typically stops at 3999, so inputs beyond that might be considered out of scope or require specific handling if the problem allows for extensions.
All identical values in a sequence that implies subtraction (e.g., 'IIII' instead of 'IV')	The conversion logic should prioritize subtractive notation over simple summation for valid cases, assuming standard Roman numeral rules.

Null or empty input string

How to Handle:

The solution should return 0 for a null or empty input string, as there are no Roman numerals to convert.

Single character Roman numeral (e.g., 'I', 'V')

How to Handle:

The solution should correctly map single characters to their corresponding integer values.

Roman numerals with subtractive notation (e.g., 'IV', 'IX', 'XL', 'XC', 'CD', 'CM')

How to Handle:

The algorithm must be designed to handle these specific combinations by checking preceding characters.

Roman numerals with repeated characters (e.g., 'III', 'XX')

How to Handle:

The solution should correctly sum the values of repeated characters.

Longest possible valid Roman numeral input

How to Handle:

The solution should scale efficiently for longer strings, ensuring performance does not degrade significantly.

Invalid Roman numeral characters (e.g., 'A', 'Z', numbers)

How to Handle:

The problem statement implies valid Roman numeral input; however, a robust solution might throw an error or return a specific indicator for invalid characters.

Roman numerals exceeding the standard representation (e.g., 'MMMM')

How to Handle:

The standard Roman numeral system typically stops at 3999, so inputs beyond that might be considered out of scope or require specific handling if the problem allows for extensions.

All identical values in a sequence that implies subtraction (e.g., 'IIII' instead of 'IV')

How to Handle:

The conversion logic should prioritize subtractive notation over simple summation for valid cases, assuming standard Roman numeral rules.