Roman Numeral to Integer: How to solve using a HashMap
A walkthrough on how we can solve this coding exercise by using a hash map
Roman numerals are represented by seven different symbols. The following symbols and their values are as follows:
Let’s start with some simple examples. The number “3” is written as III in Roman numeral, where we add the three one’s together. The number “7” is written as VII, where we add “V”, which is 5, to II, which is 2, resulting in 5+2 = 7. The number “11” is written as XI, where we add “X”, which is 10, to I, which is 1, resulting in 10+1 = 11.
With the above examples, we have them written in a way where the values are written from largest to smallest from left to right. However, there are instances where this is not the case.
For instance, “4” is not written as “IIII”. The roman numeral for 4 is written as IV. In this case, because the one is before the five, we use subtraction instead of the addition to get 4. The same principle applies to “9”, which in roman numerals is written as IX.
There are six different instances in which this principle applies:
- I can be placed before V (4)
- I can be placed before X (9)
- X can be placed before L (40)
- X can be placed before C (90)
- C can be placed before D (400)
- C can be placed before M (900)
So with these exceptions, we simply can’t just implement a solution where we add up all of the numbers — there will be instances where we have to subtract the numbers.
So what can we use to help us with this? A hash map!
Given a roman numeral, convert it to an integer
Let’s give it a try!
Note that this problem is on Leetcode (question #13). Link to the question: https://leetcode.com/problems/roman-to-integer/
Before we dive into the code, let’s see how this might look in plain English.
- Create a hash, set each key as a roman numeral and value to their corresponding value.
- Create a variable called counter, which will hold the value after each iteration. We will return counter at the end of the function
- Set a for loop to iterate the length of the input string(or roman numeral). We’ll need to create two variables with each iteration to hold the current value & the next value so we can do a comparison
- If the current value is less than the next value (for instance, IV), the counter will decrease by the current value. This is our exception rule that we went over above.
- Else, we add the current value to the counter (the current value is greater than the next value (for instance, VI)
Let’s get to it! Our first step is to create our hash map so we can look up our values in each iteration. Because we already know what roman numerals we need to use as well as the values associated with each numeral, we can easily set up a hash with key value pairs!
After setting our counter variable, we’ll need to set up our for loop and have our currentValue & nextValue variables set to the current iteration’s value & next iteration’s value, respectively. We can access these values via the romanNumerals hash we set up above.
Next, we set our conditionals using an if statement. Remember, we need to check whether the currentValue is less than nextValue. If it is, we hit one of our principles laid out previously & we subtract counter by the currentValue. On the flip side, if the currentValue is equal or greater than next value, we add counter by the currentValue.
Our final code looks like this:
There you have it! A tricky catch that we have to work with has been easily overcome with the use of a hash. With each iteration, we can simply look up the value with the hash that we created & appropriately add or subtract the value based on the order of the roman numeral.
If you came up with another approach, I would love to hear it. Let me know your thoughts & if you have any questions, feel free to reach out.
Until next time!