Roman to Integer - Short & Simple LeetCode Solution
This is another article in the series leetcode problem solutions. In this article we will be solving leetcode problem 13 Roman to Integer.
Problem Statement
Convert the given roman numeral into an integer value. Roman numerals are represented using seven different symbols as shown below:
Symbol | Value |
I | 1 |
V | 5 |
X | 10 |
L | 50 |
C | 100 |
D | 500 |
M | 1000 |
For example, in Roman numerals:
1 is written as I.
2 is written as II i.e. by adding two "ones" I+I together.
12 is written as XII which is X + II.
Number 27 is XXVII, which is XX + V + II.
Roman numerals are usually written from largest to smallest from left to right. However, there are certain exceptions to this rule, for example, 4 is not written as IIII, instead it is IV. This is written by subtracting one from five (i.e. V - I). Similarly 9 is written as IX i.e. X - I.
There are six such 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.
Note: For a quick recap of roman numerals you can refer this article.
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].
Examples
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.
Solution
So, how can we approach the problem statement?
Our objective here is to convert the given roman numeral to an equivalent integer value. If you observe carefully, you can see that we can get the required result by simply adding up all the roman numerals in the input.
For example, if s="LVIII" is the given input, its equivalent integer value is 58, which can get by adding all roman numerals in the given input, i.e.
result = L + V + I + I + I = 50 + 5 + 1 + 1 + 1 = 58.
Similarly if CCLXXXIII is the input, the result would be,
result = C + C + L + X + X + X + I + I + I = 100 + 100 + 50 + 10 + 10 + 10 + 1 + 1 + 1 = 283.
But (It cannot be that simple! There is always a "but" isn't it 😉), as stated in the problem statement, there are exceptions, we cannot always get the required result simply by adding up all the roman literals in the given input all the time.
For instance if s="CDXCVII" is the input, the correct result is 497, but if we do
result = C + D + X + C + V + I + I,
we get 100 + 500 + 10 + 100 + 5 + 1 + 1=717, which obviously is not the correct answer. The correct result should be (-C + D - X + C + V + I + I) = 497.
So, how can we detect and handle such scenarios in our code where we have to subtract some values in order to get the needed output?
Again, if you analyze the given input, for all cases where we have to do "addition only" to get the result, the adjacent numerals in the input are in decreasing order from left to right. If we consider our previous example again of s="LVIII", if we scan the input from left to right:
L >= V >= I >= I >= I
Similarly, for input s="CCLXXXIII",
C >= C >= L >= X >= X >= X >= I >= I >= I
Now, if you check the same for inputs where we have to do subtraction, you can see that it does not follow this decreasing order rule.
For example, in case of s="CDXCVII", C < D and X < C. And you will observe a similar trend if you take any other input involving subtraction.
So, what is the conclusion?
From all the above observations, we can conclude that, if s="[N1][N2][N3]...."as we read adjacent values in the given input from left to right, as long as the left numeral >= right numeral, we add the left numeral to result, otherwise we subtract it from the result. We have to repeat this procedure for all the roman numerals in input to get the final result.
Algorithm
With the understanding that we have so far, we can use the sliding window algorithm to solve this problem.
For any input s our algorithm needs to do the following set of steps:
First, take a variable to store our result, lets name this variable as result.
Traverse the given input s from left to right and compare each adjacent roman numerals.
During comparison,
If N1 >= N2, add N1 to result.
If N1 < N2, subtract N1 from result.
Move the window to the next set of adjacent numerals N2 and N3 and repeat step 3.
Once all the numerals in s are compared, result will have the final answer, return result.
To make it easier for you to understand, let me explain this algorithm with the help of an example.
Example 1
Consider s="LVIII" which is the roman numeral for 58.
First step is to create a result variable. Initially result=0.
First we compare L and V as shown in below diagram.
L > V (50 > 5), therefore we add L i.e. 50 to the result.
Next we move our window ahead by one and compare V and I.
V > I, hence we add V or 5 to the result. Now result = 50 +5 = 55.
Again we move window ahead and compare I and I.
I is equal to I, so we I to result. result = 55+1=56.
We again move the window and compare the remaining 2 numerals,
Since I is equal to I we add 1 again to the result making result=57.
Finally we add the last remaining I to the result.
Now result = 57 + 1 = 58 which is the required answer, so we return it as the final result.
Example 2
Lets now take an example involving subtraction, s="DXCIX" which is 599.
First we create variable result=0. Next we compare D and X.
D > X, therefore we add D to result.
result = 0 + 500=500
Next we compare X and C.
X < C, therefore we subtract X from result.
result = 500 - 10 = 490
Next we compare C and I.
C > I, add C to result.
result = 490 + 100 = 590
Next compare I and X.
I < X, subtract I from result.
result = 590 - 1 = 589
Finally add the remaining X to the result.
result = 589 + 10 = 599, which is the required result.
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
Code
Go Solution
Python 3 Solution
Java Solution
JavaScript Solution
C++ Solution
C Solution
Complexity Analysis
Time Complexity: O(n)
Since we iterate the given string s only once to get the result, if n is the length of s, the time complexity of this algorithm is O(n).
Space Complexity: O(1)
This algorithm uses a HashMap to store roman numerals. But since this is a fixed value (7 roman numerals) the space complexity is O(7) or in general we can say O(1).
That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.
If you found this article useful, do not forget to subscribe to our website and YouTube channel, your support motivates us to bring out more such articles in future.
You can explore more such amazing articles from code recipe in our blogs section.
Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.
