2
\$\begingroup\$

LeetCode Link

Here is the problem statement. I came up with a code that is 36% faster than other online submissions and the memory usage is 35% less than other online submissions.

Roman numerals are represented by seven different symbols: 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 one's 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 an integer, convert it to a roman numeral.

Example 1:

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

Example 2:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 3:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

1 <= num <= 3999

The code:

def intToRoman(self, num: int) -> str:
        values = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
        romanLetters =["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
        result = ""
        roman = []
        for i in range(len(values)):
            while(num >= values[i]):
                num = num - values[i]
                roman.append(romanLetters[i])
                s = ''.join(roman)
        return s

How can I make my code faster and more efficient in terms of speed and memory usage?

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Before looking at performance, I would like to suggest a few changes. Besides, your code performs above average, so it shouldn't be your main concern, and considering the longest roman numeral is only 15 characters long (3888 - MMMDCCCLXXXVIII), any performance gain will be marginal unless you plan on converting a lot of numbers.

First, make sure you include all of your code. While your intToRoman method is self-contained, it won't run without being included in a class (presumably the standard Solution class from leetCode), due to a reference to self in the method's signature.

Other remarks:

  • Your naming conventions don't follow PEP8's recommendations. If it were in another context, I'd suggest int_to_roman for the method name, but in this case, PEP8 recommends following existing (leetCode's) conventions. However, you should still name your variables in snake_case and constants in ALL_CAPS. In your case, that would be VALUES and ROMAN_LETTERS.
  • You define the variable result but don't use it. It should be removed.
  • Your method lacks a docstring. In this case you have specific requirements on the range of number accepted by the method: num should be between 1 and 3999. You can't expect the caller to guess these numbers.
  • Since you accept only a limited range of input, you should run checks on these inputs, and raise a relevant exception with a helpful message for invalid input. As it stands, your method silently accepts invalid input, outputting wrong outputs for floats or integer above 3999 and unhelpful errors for other types or negative integers (remember, type hints are just that, hints, the caller can still call the method with any type of argument)
  • I suggest you move your constants out of the method, and make them class-level constants. This would allow reuse for other method (an obvious case would be a roman to int converter), and may improve performance on repeated calls to the method (saving allocating and assigning arrays each time the function is called).
  • It is usually considered unpythonic to loop using for i in range(len(array)), and it is usually faster to use Python's powerful iterating capabilities. In your case, using zip to iterate on values and matching roman numerals would probably work best: for value, roman in zip(VALUES, ROMAN_LETTERS). Another option would be to use a dictionary instead of two arrays side-by-side.
  • The line s = ''.join(roman) looks like it's indented wrong. It is ran once for every inner loop, but it is only useful on the last pass. It looks like a typo to me and should be indented two levels less. Better yet would be to skip the assignment to a variable s and directly return that value.

Taking into account all of these remarks, the code now looks something like this:

class Solution(object):
    
    VALUES = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
    ROMAN_LETTERS =["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
    
    def intToRoman(self, num):
        """
        Converts an integer in range [1-3999] to a roman numeral
        
        :param num: the integer to convert
        :type num: int
        :return: a string representing a roman numeral
        :rtype: str
        """
        if type(num) != int:
            raise TypeError('argument must be of type int')
        if (num < 1 or num > 3999):
            raise ValueError('argument must be in range [1-3999]')
        roman = []
        for value, roman_letter in zip(self.VALUES, self.ROMAN_LETTERS):
            while(num >= value):
                num = num - value
                roman.append(roman_letter)
        return ''.join(roman)

Now, we can discuss performance. Most suggested changes should improve performance (even though it was not the main motivation for these suggestions), especially the final point. The type-checking introduces branches and will have probably a negative impact. I guess you could remove them, since leetCode is well behaved and won't call your code with funny input. However, in any real use case, you should check your inputs and test against inputs outside of what's expected.

Your code performs above average both in speed and memory usage. Beyond the low hanging fruits already addressed, anything beyond that would likely be a performance/memory tradeoff.

Since the range of input is quite small, the fastest solution would likely be to have a constant list of all roman numerals in the range [1-3999] and just look up the index. It would also be obviously wasteful memory-wise, but if 30kB of memory are an acceptable tradeoff to you, then it is valid solution.

On the other hand, you could probably improve memory efficiency by limiting your look-up arrays to just the single letters. Since all values are one character wide now, you can simply index directly into the string 'IVXLCDM', saving a bit from an array of strings. It would however hurt the complexity of the algorithm, and consequently the runtime.

One improvement that would probably save some time while keeping memory efficiency reasonable is to pre-allocate the result list: appending to a list reallocates memory multiple times to fit the new list, which is rather expensive. Something like this seems to be somewhat faster:

    result = [''] * 15
    i = 0
    for value, roman in zip(self.VALUES, self.ROMAN_LETTERS):
        while(n >= value):
            n = n - value
            result[i] = roman
            i += 1

Once again, it doesn't really matter in this particular case, but it can be a good thing to keep in mind for later on, where it might become an issue on problems that require more iterations.

\$\endgroup\$
2
\$\begingroup\$

Worry about performance and memory use when they are relevant considerations. In this problem, they are not, so keep the focus on writing simple, clear code.

Drop unneeded variables. You don't use result and barely use s.

Unify your data. The values and romanLetters data structures are logically related, but you have severed the connection. Use a dict instead, mapping each value to its symbol. [Or use a tuple-of-tuples, if your Python does not respect insertion order.]

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

The divmod() function can simplify the logic. The function tells you the two facts you need: how many times the current value can be divided into the current number; and what the new number will be after that amount is taken out. No need for the inner loop at all.

def int_to_roman(num):
    roman = ''
    for val, sym in ROMAN.items():
        n, num = divmod(num, val)
        roman += n * sym
    return roman
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.