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.
