In the previous article, we saw how to solve “Roman to Integer” problem. If you haven’t read the article yet, I strongly recommend to read it first because it will give you a good idea about how the roman numerals work.

In this article, we are going to solve a problem which is converting the integer to roman numerals. It’s quite similar to converting the roman numerals to integer but a bit harder in my opinion.

This problem is labelled as medium in LeetCode but if you never saw this problem before and not sure how the roman numerals work, it could be quite hard to come up with a solution in the first place.

However, throughout this article, we will go through every single steps with the solution and later in the future, when you see this problem again next time in the technical interview, I am confident that you will easily solve this problem.

Before we begin, please read the details of the problem in the LeetCode page here. For the solution, we are going to go with the Greedy algorithm making the best possible decision at the current time by taking out the largest symbol first.

Let’s take a look at the available roman numeral symbols first.

Roman Numeral Symbols

We are given 7 symbols representing its value.

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

Roman numerals are usually written largest to smallest from left to right so some examples are:

2 will be II
6 will be VI
27 will be XXVII

But 4 is not IIII, instead it is written as IV because the subtractive rules is applied as explained in the LeetCode description page. There are 6 additional subtractive rules.

Symbol	Value
IV	4
IX	9
XL	40
XC	90
CD	400
CM	900

Based on those symbols, let’s see some more examples in depth below.

More Examples

`3` returns `III`

1 = I
1 = I
1 = I

So it is written as III.

`58` returns `LVIII`

50 = L
5 = V
1 = I
1 = I
1 = I

There is no need for the subtractive rules so we are just finding the symbols from largest to smallest and simply combining them together.

`1994` returns `MCMXCIV`

1000 = M
900 = CM
90 = XC
4 = IV

This one is a tricky one because it needs the subtractive rules in several places. First we need a symbol for 1000 so it will start with M. And the next largest symbol needed is 900 and we need one of the subtractive rules, CM. And then the next symbol we need is 90 which is another subtractive rule, XC followed by another subtractive rule, IV for 4. Therefore, 1994 returns MCMXCIV.

Implementation in JavaScript

Here is the complete code in JavaScript.

const romanSymbols = {
  "M": 1000,
  "CM": 900,
  "D": 500,
  "CD": 400,
  "C": 100,
  "XC": 90,
  "L": 50,
  "XL": 40,
  "X": 10,
  "IX": 9,
  "V": 5,
  "IV": 4,
  "I": 1,
};

class Solution {
  intToRoman(num) {
    const roman = [];
  
    for(const symbol in romanSymbols) {
      const symbolNum = romanSymbols[symbol];

      while(symbolNum <= num) {
        num -= symbolNum;
        roman.push(symbol);
      } 
    }

    return(roman.join(''));
  }
}

Implementation steps

1. Create a hash table so that we can access and find the corresponding integer from the symbol instantly. This hash table will include both 7 symbols and 6 subtractive rules too.

We are making use of Greedy algorithm so we will have the key-value pair in the order of the integer value from largest to smallest so that we can take out the largest symbol first and then move to the next possible symbol.

const romanSymbols = {
  "M": 1000,
  "CM": 900,
  "D": 500,
  "CD": 400,
  "C": 100,
  "XC": 90,
  "L": 50,
  "XL": 40,
  "X": 10,
  "IX": 9,
  "V": 5,
  "IV": 4,
  "I": 1,
};

2. Create the class and intToRoman method. The method will accept one argument, num.

const romanSymbols = {
  "M": 1000,
  "CM": 900,
  "D": 500,
  "CD": 400,
  "C": 100,
  "XC": 90,
  "L": 50,
  "XL": 40,
  "X": 10,
  "IX": 9,
  "V": 5,
  "IV": 4,
  "I": 1,
};

class Solution {
  intToRoman(num) {
  }
}

3. Define the roman array. We are going to store each corresponding roman numeral in the array and will convert it to a string by joining them at the end and then return it.

const romanSymbols = {
  "M": 1000,
  "CM": 900,
  "D": 500,
  "CD": 400,
  "C": 100,
  "XC": 90,
  "L": 50,
  "XL": 40,
  "X": 10,
  "IX": 9,
  "V": 5,
  "IV": 4,
  "I": 1,
};

class Solution {
  intToRoman(num) {
    const roman = [];

    return(roman.join(''));
  }
}

4. Loop through the hash table. During the iteration, we are going to get the largest to smallest integer in each iteration.

const romanSymbols = {
  "M": 1000,
  "CM": 900,
  "D": 500,
  "CD": 400,
  "C": 100,
  "XC": 90,
  "L": 50,
  "XL": 40,
  "X": 10,
  "IX": 9,
  "V": 5,
  "IV": 4,
  "I": 1,
};

class Solution {
  intToRoman(num) {
    const roman = [];

    for(const symbol in romanSymbols) {
      const symbolNum = romanSymbols[symbol];
    }

    return(roman.join(''));
  }
}

The symbolNum will print all the value in the romanSymbols hash table in the order from M to I.

5. Check if the symbolNum is less than or equal to num and if so, we will deduct the symbolNum from the num because we have found the largest possible roman numeral so we don’t need the integer anymore. And we will store the corresponding symbol to the array. Let’s first see the code and take a closer look at the example throughout the loop.

const romanSymbols = {
  "M": 1000,
  "CM": 900,
  "D": 500,
  "CD": 400,
  "C": 100,
  "XC": 90,
  "L": 50,
  "XL": 40,
  "X": 10,
  "IX": 9,
  "V": 5,
  "IV": 4,
  "I": 1,
};

class Solution {
  intToRoman(num) {
    const roman = [];

    for(const symbol in romanSymbols) {
      const symbolNum = romanSymbols[symbol];

      if(symbolNum <= num) {
        num -= symbolNum;
        roman.push(symbol);
      }
    }

    return(roman.join(''));
  }
}

Let’s see the values in each iteration with the given num of 1994.

1st iteration

symbol = M
symbolNum = 1000
num = 1994

roman = [M]

Because symbolNum is smaller than num, we will deduct the symbolNum which is 1000 from the num so we no longer need to care about 1000 in the next loop. We store M to the roman array.

2nd iteration

symbol = CM
symbolNum = 900
num = 994

roman = ['M','CM']

symbolNum is smaller than num, we will deduct the symbolNum from the num for the next iteration, and store CM in the roman array.

3rd iteration

symbol = D
symbolNum = 500
num = 94

roman = ['M','CM']

Now the symbolNum is bigger than num, we will skip and do nothing. It will be the same with CD and C so we will fast-forward to 6th iteration.

6th iteration

symbol = XC
symbolNum = 90
num = 94

roman = ['M','CM', 'XC']

This time the symbolNum is smaller than num, we will deduct the symbolNum from the num and store XC in the roman array.

7th iteration

symbol = L
symbolNum = 50
num = 4

roman = ['M','CM', 'XC']

From 7th to 11th iterations, the symbolNum is bigger than the num so it will do nothing. Let’s see the 12th iteration.

12th iteration

symbol = IV
symbolNum = 4
num = 4

roman = ['M','CM', 'XC', 'IV']

The symbolNum is same as num, so we will deduct the symbolNum from the num and add IV to the roman array.

13th iteration(the last iteration)

symbol = I
symbolNum = 4
num = 0

roman = ['M','CM', 'XC', 'IV']

The symbolNum is bigger than the num, we will do nothing and as it is the last iteration, we will get out of the loop.

Because we have all the possible roman numerals in the array in the order from the largest to smallest, as on line 30, we will join the array and return it.

There is one last thing we need to update though. At the moment, the if statement (line 24) will only check one possible roman numeral and once it finds it, it will move on the next. However, let’s see another example with the given num of 3.

It will be skipped from M to IV as their value is bigger than 3.

Now for the I, it will get inside the if statement and num will be 2 and I will be pushed to the roman array. Now 2 is still smaller than I value which is 1, but because we used the if statement, the job is done and move to the return statement. And it causes returning the wrong answer, I, but it should be III.

To fix this problem, we need to keep checking until num becomes 0 so instead of if statement, we need to change it to while. So the final code will be:

const romanSymbols = {
  "M": 1000,
  "CM": 900,
  "D": 500,
  "CD": 400,
  "C": 100,
  "XC": 90,
  "L": 50,
  "XL": 40,
  "X": 10,
  "IX": 9,
  "V": 5,
  "IV": 4,
  "I": 1,
};

class Solution {
  intToRoman(num) {
    const roman = [];

    for(const symbol in romanSymbols) {
      const symbolNum = romanSymbols[symbol];

      while(symbolNum <= num) {
        num -= symbolNum;
        roman.push(symbol);
      }
    }

    return(roman.join(''));
  }
}

Python

Here is the complete code in Python.

roman_symbols = [("M", 1000), ("CM", 900), ("D", 500), ("CD", 400), ("C", 100), ("XC", 90), ("L", 50), ("XL", 40), ("X", 10), ("IX", 9), ("V", 5), ("IV", 4), ("I", 1)]

class Solution:
    def intToRoman(self, num: int) -> str:
      roman = []
      for symbol, symbol_num in roman_symbols:
        while symbol_num <= num:
          num -=symbol_num
          roman.append(symbol)
      return "".join(roman)

Big O

Time complexity

Because there is only limited number of variations with the roman numerals, up most 15 times for 3888 which is converting to MMMDCCCLXXXVIII for the loop, it is O(1) runtime.

Space complexity

There is no value increasing in size so it will be O(1) for the space complexity.