Hey everyone! Mahdi Shamlou here — back with another LeetCode classic problem.

Mahdi Shamlou

Today, we're going to solve LeetCode #13: Roman to Integer.

In the previous article, we solved LeetCode #12: Integer to Roman, where we converted an integer into a Roman numeral.

This time, we're going to do the opposite!

We are given a Roman numeral, and our task is to convert it into an integer.

Let's get started!

Mahdi Shamlou

1. Understanding the Problem

We are given a string containing a Roman numeral, and we need to convert it into an integer.

Roman numerals use seven basic symbols:

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

But there is something important we need to understand.

Sometimes, a smaller value comes before a larger value. In this case, we need to subtract the smaller value instead of adding it.

For example:

Roman Numeral Integer
IV 4
IX 9
XL 40
XC 90
CD 400
CM 900

Let's look at some examples:

  • VI = 5 + 1 = 6
  • IV = 5 - 1 = 4
  • IX = 10 - 1 = 9
  • XIV = 10 + (5 - 1) = 14

So, the main idea is simple:

If the current value is smaller than the next value, we subtract it. Otherwise, we add it.

2. My Approach

My first idea was to use a dictionary to store Roman symbols and their corresponding integer values.

Why a dictionary?

Because we can easily access the value of each Roman symbol using its key.

For example:

roman = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000 } 

Now, we need to go through the input string one character at a time.

But there is one important thing:

We need to compare the current character with the next character.

For example, imagine we have:

s = "IV" 

The first character is I, which has a value of 1.

The next character is V, which has a value of 5.

Since 1 is smaller than 5, we subtract 1 from our result.

Then we process V and add 5.

So:

0 - 1 + 5 = 4 

The final answer is 4.

This is the main idea behind my solution.

3. How Do We Compare Current and Next Values?

This is probably the most important part of the solution.

For every character, we need two values:

  • current: The value of the current Roman symbol.
  • next_value: The value of the next Roman symbol.

We can get them like this:

current = roman[s[i]] next_value = roman[s[i + 1]] if i + 1 < len(s) else 0 

There is something interesting in the second line.

What happens when we reach the last character?

There is no next character!

To avoid an index error, we check whether i + 1 is smaller than the length of the string.

If there is a next character, we get its value.

Otherwise, we use 0.

Now we can compare the two values:

if current < next_value: result -= current else: result += current 

That's it!

We don't need complicated conditions for IV, IX, XL, or other special combinations.

We only need to compare the current value with the next value.

4. My Final Python Solution

Here is my final implementation:

class Solution: def romanToInt(self, s: str) -> int: roman = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000 } result = 0 for i in range(len(s)): current = roman[s[i]] next_value = roman[s[i + 1]] if i + 1 < len(s) else 0 if current < next_value: result -= current else: result += current return result 

5. How Does It Work?

Let's use this example:

s = "MCMXCIV" 

We already know that the correct answer is 1994.

Let's see what happens at each iteration.

Current Symbol Current Value Next Value Operation Result
M 1000 100 Add 1000
C 100 1000 Subtract 900
M 1000 10 Add 1900
X 10 100 Subtract 1890
C 100 5 Add 1990
I 1 5 Subtract 1989
V 5 0 Add 1994

Let's break down the calculation:

MCMXCIV 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994 

As you can see, we don't need to recognize special combinations separately.

We just compare each character with the next one.

6. Complexity Analysis

Let's analyze the solution.

Time Complexity: O(n)

We iterate through the input string once.

For each character, we perform dictionary lookups and a simple comparison.

Both operations take O(1) time on average.

Therefore, the total time complexity is O(n), where n is the length of the input string.

Space Complexity: O(1)

We use a dictionary containing only seven Roman symbols.

We also use a few variables, such as result, current, and next_value.

The dictionary size does not grow with the input string.

Therefore, the space complexity is O(1).

Final Thoughts

This was an interesting problem, especially because it is the reverse of LeetCode #12: Integer to Roman.

In the previous problem, we used a greedy approach to build a Roman numeral.

This time, we used a dictionary and a simple comparison to convert it back into an integer.

Sometimes, the best solution is not about writing more code. It's about finding the right observation.

What do you think about this approach? Would you solve it differently?

Let me know in the comments!

You can also find my LeetCode solutions in my GitHub repository:

GitHub: mahdi0shamlou/LeetCode

Author: Mahdi Shamlou

Author: مهدی شاملو