Roman characters to Integer

Photo by Brooke Campbell on Unsplash

Algorithms are essential to understand, no matter your reason for coding, especially when searching for a computer science job. While algorithms seem tedious during a technical interview, coders use them to achieve even the most basic tasks. This blog covers the JavaScript solution to the ‘Roman to Integer’ problem on Leetcode.com. This algorithm is an excellent review as it introduces the idea of dictionaries, which can improve your code’s Big O notation.

Problem Description:

Seven different symbols represent Roman numerals: 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.

Approach:

There are several methods for creating this algorithm, but the approach is about the same.

• Loop through each character in the string of roman numerals.
• Compare the value of roman symbols from right to left, adding and subtracting the composite answer when necessary.

1. Subtractive numerals appear before a large number; therefore, looping the string in reverse order aids in identifying these situations.
2. If the next numeral in the sequence has a smaller key value than the previous entry, then subtract its value from the answer.

Code Implementation:

//first we create a dictionary containing key : value pairs of the roman numerals.
const dict = { ‘I’: 1, ‘V’:5, ‘X’:10, ‘L’:50, ‘C’:100, ‘D’:500, ‘M’:1000}
//this will allow us to do hashed value look ups which decrease run time and space capacity when compared to a switch case approach.
var romanToInt = function(s) {
//We then create a variable to hold our answer and mutate as needed.
let ans = 0
//this looping structure is how we will traverse the (s)tring in reverse
//we use the length minus 1 with ~i to create the limit and inverse index of the (s)tring
//for example if the string is 6 then i = ~5 or -6. i — is how to read indices in reverse
for(let i = s.length -1; ~i; i — ){
//we set-up j to discern the character to the right of the current
let j = i + 1
//num is the value of the current character in the loop.
let num = dict[s.charAt(i)]
//We get the value through a look-up of the dictionary we created earlier.
//compare the current character’s value to the numeral on the right.
if(num < dict[s.charAt(j)]){
//if the current numeral’s value is smaller than the previous, then we subtract that character’s worth from the whole.
ans -= num
}
//in all other cases, we want to add the num to the answer.
else ans += num
}
return ans
};

Big O 3999/3999 test cases passed :

• Runtime: 160 ms (beats 85.24% of JavaScript submissions)
• Memory Usage: 45 MB (beats 76.46% of JavaScript submissions)

Useful Lesson:

• How to loop a string in reverse
• Create a dictionary
• Do dictionary look-ups
• Conditionals

Leave a like if this review was helpful and comment with any questions. Please refer to the resources below for further guidance.

Resources:

The problem

Roman to Integer - LeetCode

How to reverse a string

Three Ways to Reverse a String in JavaScript

What is the ~ in JavaScript

JavaScript Operators Reference

How to make and use a dictionary

How to create dictionary and add key-value pairs dynamically? - GeeksforGeeks

JavaScript conditionals

JavaScript if else else if